Comparing Growth Rates of Functions 289(3) F : N -+ [0, cc), given by the rule F(n) = n - 2, is undefined for n = 0, 1 (since
0 - 2 and 1 - 2 are less than 0) but is defined for all n > 2.5.1.2 Properties of Asymptotic Domination
Most of the theorems in this section are chosen so that we could prove some fundamental
results about how polynomial functions are related with respect to complexity. Theorems
1-4 that follow are useful for that purpose but apply much more generally to arbitrary
functions.
Theorem 1. Let F : N --* [0, cc), and let a E (0, cc). Then, F asymptotically dominates
a .F.
Proof. By the general assumption, there is a natural number No such that F(n) is defined
for all n > No. Therefore, a • F(n) e [0, cc) for all n such that n > No. Now, choose
c = a. Then, for all n > No,
a • F(n) < c. F(n)Therefore, a • F E O(F). U
Corollary 1: For any positive real number a and any F : N -+ [0, cc), both a • F E
O(F) and F E O(a • F).
Proof. By Theorem 1, a • F E O(F). However, since a > 0, (I/a) also exists and is
positive. So, since F = (1/a)(a • F), F E 0(a -F). N
In the case a = 1 in Theorem 1, the result says that the relation asymptotically domi-
nates is reflexive.
Theorem 2 tells us that the asymptotically dominated relationship is a transitive
relation.
Theorem 2. Let F, G, H :N --* [0, ), with H E O(G) and G c O(F). Then, H E
O(F).
Proof. Since H e O(G), there are constants CH E [0, cc) and NH E N such that for all
n > NH, G(n) and H(n) are both defined and H(n) < cHG(n). Since G ( O(F), there
are constants CG E [0, oo) and NG E N such that for all n > NG, F(n) and G(n) are both
defined and G(n) < cG F(n). Let No be the maximum of NG and NH, and let c = CH -cG.
Then, for any n > No,
H(n) < CH • G(n)
< CH • (co • F(n))
= (cH" CG) F(n)
= c. F(n)Therefore, H E O(F). 0
One feature in the proof of Theorem 2 deserves comment. We picked No to be the
maximum of NG and NH and c to be cn • CG. We do not know whether smaller values for
c or No might have "worked": That depends on further information about G, H, cG, CH,