Java Reference
In-Depth Information
To minimize the effects of worst-case behavior, the algorithm's best strategy is
to maximize the minimum improvement in strength by balancing the strengths of
any two competitors. From the algorithm's point of view, the best outcome is that
an element doubles in strength. This happens whenever a = b, where a and b are
the strengths of the two elements being compared. All strengths begin at zero, so
the winner must make at least k comparisons when 2
k1
< n 2
k
. Thus, there
must be at least n + dlog ne 2 comparisons. So our algorithm is optimal.
15.5
State Space Lower Bounds Proofs
We now consider the problem of finding both the minimum and the maximum from
an (unsorted) list of values. This might be useful if we want to know the range of
a collection of values to be plotted, for the purpose of drawing the plot's scales.
Of course we could find them independently in 2n 2 comparisons. A slight
modification is to find the maximum in n 1 comparisons, remove it from the
list, and then find the minimum in n 2 further comparisons for a total of 2n 3
comparisons. Can we do better than this?
Before continuing, think a moment about how this problem of finding the mini-
mum and the maximum compares to the problem of the last section, that of finding
the second biggest value (and by implication, the maximum). Which of these two
problems do you think is harder? It is probably not at all obvious to you that one
problem is harder or easier than the other. There is intuition that argues for ei-
ther case. On the one hand intuition might argue that the process of finding the
maximum should tell you something about the second biggest value, more than
that process should tell you about the minimum value. On the other hand, any
given comparison tells you something about which of two can be a candidate for
maximum value, and which can be a candidate for minimum value, thus making
progress in both directions.
We will start by considering a simple divide-and-conquer approach to finding
the minimum and maximum. Split the list into two parts and find the minimum and
maximum elements in each part. Then compare the two minimums and maximums
to each other with a further two comparisons to get the final result. The algorithm
is shown in Figure 15.3.
The cost of this algorithm can be modeled by the following recurrence.
8
<
:
0 n = 1
1 n = 2
T(bn=2c) + T(dn=2e) + 2 n > 2
T(n) =
This is a rather interesting recurrence, and its solution ranges between 3n=22
(when n = 2
i
or n = 2
1
1) and 5n=32 (when n = 32
i
). We can infer from
this behavior that how we divide the list affects the performance of the algorithm.
