Java Reference
In-Depth Information
root of that:
p
10 3:16. Thus, the algorithm with higher growth rate not only
solves a smaller problem in a given time in the first place, it also receives less of
a speedup from a faster computer. As computers get ever faster, the disparity in
problem sizes becomes ever greater.
The algorithm with growth rate T(n) = 5n log n improves by a greater amount
than the one with quadratic growth rate, but not by as great an amount as the algo-
rithms with linear growth rates.
Note that something special happens in the case of the algorithm whose running
time grows exponentially. In Figure 3.1, the curve for the algorithm whose time is
proportional to 2
n
goes up very quickly. In Figure 3.3, the increase in problem
size on the machine ten times as fast is shown to be about n + 3 (to be precise,
it is n + log
2
10). The increase in problem size for an algorithm with exponential
growth rate is by a constant addition, not by a multiplicative factor. Because the
old value of n was 13, the new problem size is 16. If next year you buy another
computer ten times faster yet, then the new computer (100 times faster than the
original computer) will only run a problem of size 19. If you had a second program
whose growth rate is 2
n
and for which the original computer could run a problem
of size 1000 in an hour, than a machine ten times faster can run a problem only of
size 1003 in an hour! Thus, an exponential growth rate is radically different than
the other growth rates shown in Figure 3.3. The significance of this difference is
explored in Chapter 17.
Instead of buying a faster computer, consider what happens if you replace an
algorithm whose running time is proportional to n
2
with a new algorithm whose
running time is proportional to n log n. In the graph of Figure 3.1, a fixed amount of
time would appear as a horizontal line. If the line for the amount of time available
to solve your problem is above the point at which the curves for the two growth
rates in question meet, then the algorithm whose running time grows less quickly
is faster. An algorithm with running time T(n) = n
2
requires 1024 1024 =
1; 048; 576 time steps for an input of size n = 1024. An algorithm with running
time T(n) = n log n requires 1024 10 = 10; 240 time steps for an input of
size n = 1024, which is an improvement of much more than a factor of ten when
compared to the algorithm with running time T(n) = n
2
. Because n
2
> 10n log n
whenever n > 58, if the typical problem size is larger than 58 for this example, then
you would be much better off changing algorithms instead of buying a computer
ten times faster. Furthermore, when you do buy a faster computer, an algorithm
with a slower growth rate provides a greater benefit in terms of larger problem size
that can run in a certain time on the new computer.
