286 CHAPTER 5 Analysis of Algorithms
Example 2. Let F 1 , G I N --* [ 0, oo )where F, (n) = n and
Sn-2 forn>2
0 otherwise
as shown in Figure 5.1.y00(^10) 0oo
8 0 X
00 X
6 0 xX
0 x
(^0) o
x
2 4 6 8 10
Figure 5.1 F, (n) and G, (n).
Then, F 1 E O(GI) and G 1 E O(F 1 ).
Solution. Obviously, F 1 (n) > G 1 (n) for all n. Intuitively, however, the functions seem
to grow at the same rate. Indeed, for n > 2, their graphs have the same slope.
Showing that G 1 e 0(F 1 ) is easy. Clearly, G I (x) is always less than or equal to F1 (x).
So, pick c = 1 and No = 0, and the definition of asymptotic domination is satisfied.
To show F 1 E 0(G 1 ) is only slightly harder: Let c = 2, and let No = 4. For all n such
that n > 4, n - 4 > 0; hence,
FI(n) = n=n+0
< n + (n - 4)
= 2n -4
= 2(n - 2)
= 2. Gl(x)
= c. GI(x)
In Example 2, G 1 (n) could have been zero for all n < No where No > 2, and a similar
proof would still work.
Example 3 shows that behavior at a single point will make no difference to the
0-relation.
Example 3. Let F 2 , G 2 : N --* [0, co) where F 2 (n) = n and
G 2 (n) = 100,000,000,000 for n = 0
n otherwise
Then, F 2 E O(G 2 ) and G 2 E O(F 2 ).