Discrete Mathematics for Computer Science

Comparing Growth Rates of Functions 2817

Solution. Here, G 2 (0) is much larger than F 2 (0). For all other values of n, we have

G 2 (n) = F 2 (n). The intuition is that one value, or any finite number of values, makes no

difference to the growth rate of a function.

To show that F 2 c O(G 2 ) and G 2 E O(F 2 ), choose c = 1 and No = 1 for both impli-

cations. Then, for all n such that n > 1, it follows that

F 2 (n) < 1 • G2(n)

and

G 2 (n) < 1 - F 2 (n)

This finishes the proof. U

The values of F 2 and G 2 in Example 3 could have differed at any point-say, no. At

no, let G 2 (no) = F 2 (no) + 100,000. The only adjustment to the proof would be to choose

No such that No > no.

We will see in Example 4 what is involved in proving that one function is not asymp-

totically dominated by another function. The functions in Example 4 show that the relation

asymptotically dominates is not a symmetric relation.

Example 4. Let F 4 , G4 N -- [0, oo) where F 4 (n) = n and G 4 (n) -n^2 , as shown in

Figure 5.2.

y

100 xG4(n)n21X

o F 4 (n) =

8 0 0 F^4

) x(

x

60 x

x

40 x

x

20 X

x

0 0 0 0 0 0 00 0

2 4 6 8 10

Figure 5.2 F 4 (n) = n and G 4 (n) = n^2.

Then, F 4 E O(G 4 ), and G 4 0 O(F 4 ).

Solution. From the graphs of the functions, G 4 seems to grow faster than F 4 .More im-
portantly, G 4 seems to grow faster than 2 • F 4 , faster than 3 • F 4 , and for each real number
c such that c > 0, faster than c • F 4 , as shown in Figure 5.3 on page 288.
The intuition is that G 4 grows much faster than F 4 .We verify this intuition by proving
that (a) F 4 E O(G 4 ) but (b) G 4 0 O(F 4 ):

(a) Pick c = 1 and No = 1. For n > 1, it is obvious that n^2 > n.