Java Reference
In-Depth Information
f(n) n n
0
Change n
0
/n
10n
n
0
= 10n
1000
10; 000
10
n
0
=
10n
20n
500
5000
10
1842
p
10n
< n
0
< 10n
5n log n
250
7:37
n
0
=
p
10n
2n
2
70
223
3:16
2
n
n
0
= n + 3
13
16
Figure3.3
The increase in problem size that can be run in a fixed period of time
on a computer that is ten times faster. The first column lists the right-hand sides
for each of five growth rate equations from Figure 3.1. For the purpose of this
example, arbitrarily assume that the old machine can run 10,000 basic operations
in one hour. The second column shows the maximum value for n that can be run
in 10,000 basic operations on the old machine. The third column shows the value
for n
0
, the new maximum size for the problem that can be run in the same time
on the new machine that is ten times faster. Variable n
0
is the greatest size for the
problem that can run in 100,000 basic operations. The fourth column shows how
the size of n changed to become n
0
on the new machine. The fifth column shows
the increase in the problem size as the ratio of n
0
to n.
If your algorithm's growth rate is linear (i.e., if the equation that describes the
running time on input size n is T(n) = cn for some constant c), then 100,000
records on the new machine will be sorted in the same time as 10,000 records on
the old machine. If the algorithm's growth rate is greater than cn, such as c
1
n
2
,
then you will not be able to do a problem ten times the size in the same amount of
time on a machine that is ten times faster.
How much larger a problem can be solved in a given amount of time by a faster
computer? Assume that the new machine is ten times faster than the old. Say that
the old machine could solve a problem of size n in an hour. What is the largest
problem that the new machine can solve in one hour? Figure 3.3 shows how large
a problem can be solved on the two machines for five of the running-time functions
from Figure 3.1.
This table illustrates many important points. The first two equations are both
linear; only the value of the constant factor has changed. In both cases, the machine
that is ten times faster gives an increase in problem size by a factor of ten. In other
words, while the value of the constant does affect the absolute size of the problem
that can be solved in a fixed amount of time, it does not affect the improvement in
problem size (as a proportion to the original size) gained by a faster computer. This
relationship holds true regardless of the algorithm's growth rate: Constant factors
never affect the relative improvement gained by a faster computer.
An algorithm with time equation T(n) = 2n
2
does not receive nearly as great
an improvement from the faster machine as an algorithm with linear growth rate.
Instead of an improvement by a factor of ten, the improvement is only the square
