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 implications. 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 asymptotically 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 importantly, 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.