Analysis of Algorithms : An Active Learning Approach

1.4 RATES OF GROWTH 21

the smallest value is x^2 / 8 and the one with the largest value is x + 10. We can

see, however, that as the value of x gets large, x^2 / 8 becomes and stays the

function with the largest value.

Putting all of this together means that as we analyze algorithms, we will be

interested in which rate of growth class an algorithm falls into rather than try-

ing to find out exactly how many of each operation are done by the algorithm.

When we consider the relative “size” of a function, we will do so for large val-

ues of x, not small ones.

Some of the common classes of algorithms can be seen in the chart in Fig.

1.2. In this chart, we show the value for these classes over a wide range of

input sizes. You can see that when the input is small, there is not a significant

difference in the values, but once the input value gets large, there is a big dif-

ference. This reinforces what we saw in the graph in Fig. 1.1. Because of this,

we will always consider what happens when the size of the input is large,

because small input sets can hide rather dramatic differences.

The data in Figs. 1.1 and 1.2 illustrate a second point. Because the faster-

growing functions increase at such a significant rate, they quickly dominate the

slower-growing functions. This means that if we determine that an algorithm’s

complexity is a combination of two of these classes, we will frequently ignore

all but the fastest growing of these terms. For example, if we analyze an algo-

1

2

5

10

15

20

30

40

50

60

70

80

90

100

1.0

2.0

5.0

10.0

15.0

20.0

30.0

40.0

50.0

60.0

70.0

80.0

90.0

100.0

0.0

2.0

11.6

33.2

58.6

86.4

147.2

212.9

282.2

354.4

429.0

505.8

584.3

664.4

0.0

1.0

2.3

3.3

3.9

4.3

4.9

5.3

5.6

5.9

6.1

6.3

6.5

6.6

Ignnn Ig n

1.0

4.0

25.0

100.0

225.0

400.0

900.0

1600.0

2500.0

3600.0

4900.0

6400.0

8100.0

10000.0

1.0

8.0

125.0

1000.0

3375.0

8000.0

27000.0

64000.0

125000.0

216000.0

343000.0

512000.0

729000.0

1000000.0

2.0

4.0

32.0

1024.0

32768.0

1048576.0

1073741824.0

1099511627776.0

1125899906842620.0

1152921504606850000.0

1180591620717410000000.0

1208925819614630000000000.0

1237940039285380000000000000.0

1267650600228230000000000000000.0

n^2 n^32 n

■FIGURE 1.2
Common algorithm
classes