Lower Bounds - Data Structures and Algorithm Analysis - page 487

Now we know precisely what we are aiming for when designing an algorithm:
We want to find an algorithm who's upper bound matches the lower bound of the
problem. Putting together all that we know so far about algorithms, we can organize
our thinking into the following “algorithm for designing algorithms.” 2
If the upper and lower bounds match,
then stop,
else if the bounds are close or the problem isn't important,
then stop,
else if the problem definition focuses on the wrong thing,
then restate it,
else if the algorithm is too slow,
then find a faster algorithm,
else if lower bound is too weak,
then generate a stronger bound.
We can repeat this process until we are satisfied or exhausted.
This brings us smack up against one of the toughest tasks in analysis. Lower
bounds proofs are notoriously difficult to construct. The problem is coming up with
arguments that truly cover all of the things that any algorithm possibly could do.
The most common fallacy is to argue from the point of view of what some good
algorithm actually does do, and claim that any algorithm must do the same. This
simply is not true, and any lower bounds proof that refers to specific behavior that
must take place should be viewed with some suspicion.
Let us consider the Towers of Hanoi problem again. Recall from Section 2.5
that our basic algorithm is to move n 1 disks (recursively) to the middle pole,
move the bottom disk to the third pole, and then move n1 disks (again recursively)
from the middle to the third pole. This algorithm generates the recurrence T(n) =
2T(n 1) + 1 = 2 n 1. So, the upper bound for our algorithm is 2 n 1. But is
this the best algorithm for the problem? What is the lower bound for the problem?
For our first try at a lower bounds proof, the “trivial” lower bound is that we
must move every disk at least once, for a minimum cost of n. Slightly better is to
observe that to get the bottom disk to the third pole, we must move every other disk
at least twice (once to get them off the bottom disk, and once to get them over to
the third pole). This yields a cost of 2n1, which still is not a good match for our
algorithm. Is the problem in the algorithm or in the lower bound?
We can get to the correct lower bound by the following reasoning: To move the
biggest disk from first to the last pole, we must first have all of the other n1 disks
out of the way, and the only way to do that is to move them all to the middle pole
(for a cost of at least T(n 1)). We then must move the bottom disk (for a cost of
2 This is a minor reformulation of the “algorithm” given by Gregory J.E. Rawlins in his book
“Compared to What?”