Java Reference
In-Depth Information
15
Lower Bounds
How do I know if I have a good algorithm to solve a problem? If my algorithm runs
in (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.
In Section 3.6 we defined 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. This
is the subject of Chapter 17. 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 proof from Section 7.9 that the problem of
sorting is O(n log n) in the worst case.
Section 15.1 reviews the concept of a lower bound for a problem and presents
the basic “algorithm” for finding a good algorithm. Section 15.2 discusses lower
bounds on searching in lists, both those that are unordered and those that are or-
dered. Section 15.3 deals with finding the maximum value in a list, and presents a
model for selection based on building a partially ordered set. Section 15.4 presents
485
 
Search WWH ::




Custom Search