Java Reference
In-Depth Information
for a faster algorithm? Many have tried, without success. Fortunately (or perhaps
unfortunately?), Chapter 7 also includes a proof that any sorting algorithm must
have running time in (n log n) in the worst case.
2
This proof is one of the most
important results in the field of algorithm analysis, and it means that no sorting
algorithm can possibly run faster than cn log n for the worst-case input of size n.
Thus, we can conclude that the problem of sorting is (n log n) in the worst case,
because the upper and lower bounds have met.
Knowing the lower bound for a problem does not give you a good algorithm.
But it does help you to know when to stop looking. If the lower bound for the
problem matches the upper bound for the algorithm (within a constant factor), then
we know that we can find an algorithm that is better only by a constant factor.
3.7
Common Misunderstandings
Asymptotic analysis is one of the most intellectually difficult topics that undergrad-
uate computer science majors are confronted with. Most people find growth rates
and asymptotic analysis confusing and so develop misconceptions about either the
concepts or the terminology. It helps to know what the standard points of confusion
are, in hopes of avoiding them.
One problem with differentiating the concepts of upper and lower bounds is
that, for most algorithms that you will encounter, it is easy to recognize the true
growth rate for that algorithm. Given complete knowledge about a cost function,
the upper and lower bound for that cost function are always the same. Thus, the
distinction between an upper and a lower bound is only worthwhile when you have
incomplete knowledge about the thing being measured. If this distinction is still not
clear, reread Section 3.6. We use -notation to indicate that there is no meaningful
difference between what we know about the growth rates of the upper and lower
bound (which is usually the case for simple algorithms).
It is a common mistake to confuse the concepts of upper bound or lower bound
on the one hand, and worst case or best case on the other. The best, worst, or
average cases each give us a concrete input instance (or concrete set of instances)
that we can apply to an algorithm description to get a cost measure. The upper and
lower bounds describe our understanding of the growth rate for that cost measure.
So to define the growth rate for an algorithm or problem, we need to determine
what we are measuring (the best, worst, or average case) and also our description
for what we know about the growth rate of that cost measure (big-Oh, , or ).
The upper bound for an algorithm is not the same as the worst case for that
algorithm for a given input of size n. What is being bounded is not the actual cost
(which you can determine for a given value of n), but rather the growth rate for the
2
While it is fortunate to know the truth, it is unfortunate that sorting is (nlogn) rather than
(n)!
