2.4.1 Getting a faster computer

How much larger problems a faster computer solve in the same amount of time? Say that the old machine could solve a problem of size $n$ in an hour, and that the new machine is ten times faster than the old. What is the largest problem that the new machine can solve in one hour? Table 2.1 shows just that for five running-time functions.

Explanations:

• The first column lists the right-hand sides for five growth rate equations.
• 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'$, 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'$ 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'$ on the new machine.
• The fifth column shows the increase in problem size as the ratio of $n'$ to $n$.

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 root of that: $\sqrt{10} \approx 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) = 5 n \log n$ improves by a greater amount than the one with quadratic growth rate, but not by as great an amount as the algorithms with linear growth rates.

Note that something special happens in the case of the algorithm whose running time grows exponentially. If you look at its plot on a graph, the curve for the algorithm whose time is proportional to $2^n$ goes up very quickly as $n$ grows. The increase in problem size on the machine ten times as fast is 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 the table. The significance of this difference is an important topic in computational complexity theory.

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 a graph relating growth rate functions to input size, 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 $1000 \times 1000 = 1,000,000$ time steps for an input of size $n=1000$. An algorithm with running time $T(n) = n \log n$ requires $1000 \times 10 = 10,000$ time steps for an input of size $n = 1000$, 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 > 10 n \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.

2.4.2 Comparing different growth rates

The growth rate for an algorithm is the rate at which the cost of the algorithm grows as the size of its input grows. Figure 2.1 shows a graph for six equations, each meant to describe the running time for a particular program or algorithm. A variety of growth rates that are representative of typical algorithms are shown.

The two equations labeled $10n$ and $20n$ are graphed by straight lines. A growth rate of $cn$ (for $c$ any positive constant) is often referred to as a linear growth rate or running time. This means that as the value of $n$ grows, the running time of the algorithm grows in the same proportion. Doubling the value of $n$ roughly doubles the running time. An algorithm whose running-time equation has a highest-order term containing a factor of $n^2$ is said to have a quadratic growth rate. In the figure, the line labeled $2n^2$ represents a quadratic growth rate. The line labeled $2^n$ represents an exponential growth rate. This name comes from the fact that $n$ appears in the exponent. The line labeled $n!$ also grows exponentially.

As you can see from the figure, the difference between an algorithm whose running time has cost $T(n) = 10n$ and another with cost $T(n) = 2n^2$ becomes tremendous as $n$ grows. For $n > 5$, the algorithm with running time $T(n) = 2n^2$ is already much slower. This is despite the fact that $10n$ has a greater constant factor than $2n^2$. Comparing the two curves marked $20n$ and $2n^2$ shows that changing the constant factor for one of the equations only shifts the point at which the two curves cross. For $n>10$, the algorithm with cost $T(n) = 2n^2$ is slower than the algorithm with cost $T(n) = 20n$. This graph also shows that the equation $T(n) = 5 n \log n$ grows somewhat more quickly than both $T(n) = 10 n$ and $T(n) = 20 n$, but not nearly so quickly as the equation $T(n) = 2n^2$. For constants $a, b > 1, n^a$ grows faster than either $\log^b n$ or $\log n^b$. Finally, algorithms with cost $T(n) = 2^n$ or $T(n) = n!$ are prohibitively expensive for even modest values of $n$. Note that for constants $a, b \geq 1, a^n$ grows faster than $n^b$.

We can get some further insight into relative growth rates for various algorithms from Table 2.2 below. Most of the growth rates that appear in typical algorithms are shown, along with some representative input sizes. Once again, we see that the growth rate has a tremendous effect on the resources consumed by an algorithm.