Java Reference
In-Depth Information
3.4
Asymptotic Analysis
Despite the larger constant for the curve labeled 10n in Figure 3.1, 2n
2
crosses
it at the relatively small value of n = 5. What if we double the value of the
constant in front of the linear equation? As shown in the graph, 20n is surpassed
by 2n
2
once n = 10. The additional factor of two for the linear growth rate does
not much matter. It only doubles the x-coordinate for the intersection point. In
general, changes to a constant factor in either equation only shift where the two
curves cross, not whether the two curves cross.
When you buy a faster computer or a faster compiler, the new problem size
that can be run in a given amount of time for a given growth rate is larger by the
same factor, regardless of the constant on the running-time equation. The time
curves for two algorithms with different growth rates still cross, regardless of their
running-time equation constants. For these reasons, we usually ignore the con-
stants when we want an estimate of the growth rate for the running time or other
resource requirements of an algorithm. This simplifies the analysis and keeps us
thinking about the most important aspect: the growth rate. This is called asymp-
totic algorithm analysis. To be precise, asymptotic analysis refers to the study of
an algorithm as the input size “gets big” or reaches a limit (in the calculus sense).
However, it has proved to be so useful to ignore all constant factors that asymptotic
analysis is used for most algorithm comparisons.
It is not always reasonable to ignore the constants. When comparing algorithms
meant to run on small values of n, the constant can have a large effect. For exam-
ple, if the problem is to sort a collection of exactly five records, then an algorithm
designed for sorting thousands of records is probably not appropriate, even if its
asymptotic analysis indicates good performance. There are rare cases where the
constants for two algorithms under comparison can differ by a factor of 1000 or
more, making the one with lower growth rate impractical for most purposes due to
its large constant. Asymptotic analysis is a form of “back of the envelope” esti-
mation for algorithm resource consumption. It provides a simplified model of the
running time or other resource needs of an algorithm. This simplification usually
helps you understand the behavior of your algorithms. Just be aware of the limi-
tations to asymptotic analysis in the rare situation where the constant is important.
3.4.1
Upper Bounds
Several terms are used to describe the running-time equation for an algorithm.
These terms — and their associated symbols — indicate precisely what aspect of
the algorithm's behavior is being described. One is the upper bound for the growth
of the algorithm's running time. It indicates the upper or highest growth rate that
the algorithm can have.
