31.1. Chapter Introduction: Lower Bounds¶

How do I know if I have a good algorithm to solve a problem? If my algorithm runs in \(\Theta(n \log n)\) time, is that good? It would be if I were sorting the records stored in an array. But it would be terrible if I were searching the array for the largest element. The value of an algorithm must be determined in relation to the inherent complexity of the problem at hand.

We define the upper bound for a problem to be the upper bound of the best algorithm we know for that problem, and the lower bound to be the tightest lower bound that we can prove over all algorithms for that problem. While we usually can recognize the upper bound for a given algorithm, finding the tightest lower bound for all possible algorithms is often difficult, especially if that lower bound is more than the "trivial" lower bound determined by measuring the amount of input that must be processed.

The benefits of being able to discover a strong lower bound are significant. In particular, when we can make the upper and lower bounds for a problem meet, this means that we truly understand our problem in a theoretical sense. It also saves us the effort of attempting to discover more (asymptotically) efficient algorithms when no such algorithm can exist.

Often the most effective way to determine the lower bound for a problem is to find a reduction to another problem whose lower bound is already known. However, this approach does not help us when we cannot find a suitable "similar problem". Our focus in this chapter is discovering and proving lower bounds from first principles. Our most significant example of a lower bounds argument so far is the sorting lower bound proof, which shows that the problem of sorting has a lower bound of \(O(n \log n)\) in the worst case.

The lower bound for the problem is the tightest (highest) lower bound that we can prove for all possible algorithms that solve the problem. [1] This can be a difficult bar, given that we cannot possibly know all algorithms for any problem, because there are theoretically an infinite number. However, we can often recognize a simple lower bound based on the amount of input that must be examined. For example, we can argue that the lower bound for any algorithm to find the maximum-valued element in an unsorted list must be \(\Omega(n)\) because any algorithm must examine all of the inputs to be sure that it actually finds the maximum value.

In the case of maximum finding, the fact that we know of a simple algorithm that runs in \(O(n)\) time, combined with the fact that any algorithm needs \(\Omega(n)\) time, is significant. Because our upper and lower bounds meet (within a constant factor), we know that we indeed have a "good" algorithm for solving the problem. It is possible that someone can develop an implementation that is a "little" faster than an existing one, by a constant factor. But we know that its not possible to develop one that is asymptotically better.

We must be careful about how we interpret this last statement, however. The world is certainly better off for the invention of Quicksort, even though Mergesort was available at the time. Quicksort is not asymptotically faster than Mergesort, yet is not merely a "tuning" of Mergesort either. Quicksort is a substantially different approach to sorting. So even when our upper and lower bounds for a problem meet, there are still benefits to be gained from a new, clever algorithm.

So now we have an answer to the question "How do I know if I have a good algorithm to solve a problem?" An algorithm is good (asymptotically speaking) if its upper bound matches the problem's lower bound. If they match, then we know to stop trying to find an (asymptotically) faster algorithm. What if the (known) upper bound for our algorithm does not match the (known) lower bound for the problem? In this case, we might not know what to do. Is our upper bound flawed, and the algorithm is really faster than we can prove? Is our lower bound weak, and the true lower bound for the problem is greater? Or is our algorithm simply not the best?

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]

We can repeat this process until we are either 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. 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 \(n-1\) disks (again recursively) from the middle to the third pole. This algorithm generates the recurrence \(\mathbf{T}(n) = 2\mathbf{T}(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 \(2n - 1\), 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 \(n-1\) 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 \(\textbf{T}(n-1)\)). We then must move the bottom disk (for a cost of 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 \(\textbf{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:

1. Not all disks need to start on the first pole.
2. 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.