g., in a double nested loop).
2n Exponential: when n doubles, run time squares. This is often the result of a natural, ???brute force???
solution. Such problems are not computable in a reasonable time when the problem becomes
at all large.
Table 2-1
A factorial order of growth is even more extreme than an exponential order of growth. For example, there
are about 3.6 million permutations of 10 cities, but more than 2 trillion billion permutations of 20. If the computer
can compute the distance for a million permutations a second, the TSP problem will take 1.8 seconds for
10 cities, but tens of thousands of years for 20 cities.
Figure 2-2 shows the rates of growth for lg n, n, n(lg n), n2, 2n, and n!
Table 2.1 summarizes some different orders of growth, and the characteristics of associated algorithms.
ALGORITHMS AS TECHNOLOGY
It??™s pretty exciting to buy a new computer with twice, four times, or even ten times the clock rate of the old
computer. Many people think of computer hardware speed as the measure of technological advance. Having
discussed algorithms and their performance, consider whether a better algorithm on a slower computer might
be better than a slower algorithm on a faster computer.
Pages:
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74