Java Reference
In-Depth Information
at least one). After that, we must move the n 1 remaining disks from the middle
pole to the third pole (for a cost of at least T(n 1)). Thus, no possible algorithm
can solve the problem in less than 2
n
1 steps. Thus, our algorithm is optimal.
3
Of course, there are variations to a given problem. Changes in the problem
definition might or might not lead to changes in the lower bound. Two possible
changes to the standard Towers of Hanoi problem are:
• Not all disks need to start on the first pole.
• Multiple disks can be moved at one time.
The first variation does not change the lower bound (at least not asymptotically).
The second one does.
15.2
Lower Bounds on Searching Lists
In Section 7.9 we presented an important lower bounds proof to show that the
problem of sorting is (n log n) in the worst case. In Chapter 9 we discussed a
number of algorithms to search in sorted and unsorted lists, but we did not provide
any lower bounds proofs to this important problem. We will extend our pool of
techniques for lower bounds proofs in this section by studying lower bounds for
searching unsorted and sorted lists.
15.2.1
Searching in Unsorted Lists
Given an (unsorted) list L of n elements and a search key K, we seek to identify one
element in L which has key value K, if any exists. For the rest of this discussion,
we will assume that the key values for the elements in L are unique, that the set of
all possible keys is totally ordered (that is, the operations <, =, and > are defined
for all pairs of key values), and that comparison is our only way to find the relative
ordering of two keys. Our goal is to solve the problem using the minimum number
of comparisons.
Given this definition for searching, we can easily come up with the standard
sequential search algorithm, and we can also see that the lower bound for this prob-
lem is “obviously” n comparisons. (Keep in mind that the key K might not actually
appear in the list.) However, lower bounds proofs are a bit slippery, and it is in-
structive to see how they can go wrong.
Theorem15.1
The lower bound for the problem of searching in an unsorted list
is n comparisons.
3
Recalling the advice to be suspicious of any lower bounds proof that argues a given behavior
“must” happen, this proof should be raising red flags. However, in this particular case the problem is
so constrained that there really is no (better) alternative to this particular sequence of events.
