Discrete Mathematics for Computer Science

292 CHAPTER 5 Analysis of Algorithms

Theorem 5. Let kI, k 2 e R with 0 < kl < k 2 .Let xkl and xk2 be functions of x, where

x E R. Then:

(a) xk 1 E O(xk2)

(b) xk2 g O(xkx)

Proof. Similar to that for Example 4. The details are left as an exercise for the reader.

Corollary 3: Let i, j E N with i < j. Let ni and ni be functions of n where n e N.

Then:

(a) n i E O(nj)

(b) nj e 0(n')

Theorem 5 is a first step in determining how polynomials of different degrees are re-

lated by the relation asymptotically dominates. For example, n^5 E O(n^8 ), but n^8 0 O(n^5 ).

Both Theorem 1 in Section 5.1.2 and Theorem 5 tell us how monomials are related. The-

orem 3 in Section 5.1.2 could be used to build polynomials from the individual terms

(monomials). In Theorem 6, we show how you can prove directly that a polynomial and its

terms are related to the monomial that is its highest power.

Theorem 6. For a polynomial function of degree k:

P(n) = ak nk + ak-1 nk-I +... + a2 n2 + al n + ao

Therefore:

(a) P(n) E O(nk)

(b) n k e O(P(n))

Motivation for Proof. Consider the polynomial x^3 - 3x^2 - 1. For x = 10, the value

of 103 contributes approximately 70 percent of the value of this polynomial at x = 10.

For x = 100, the value of 103 contributes approximately 97 percent of the value of the

polynomial at x = 100. So, the intuition is that for large enough values of n, or all n

greater that some No, P(n) is almost the same as ak • nk and, hence, grows approximately

as fast. The major task of the proof is to establish that intuition. We will make no effort to

choose No as small as possible. Rather, we will choose an No that makes the proof easy.

(Part (a) can also be proved using Theorem 5 and Corollary 2.)

Proof. Set

No 2. FJak-1l+ / lak-2I±+'"+ ak Jai l+ ao1I 1 +2

We leave it as an exercise for the reader to show that for all n > No,

1 k <

nk _ •ak n

< •ak P(n) <

Choose No as above and c = (^3 /^2 )ak. Then, P(n) < (^3 /^2 )ak nfk for all n > No. This

proves part (a). Now, choose No as above and c =^2 /ak. Then, nfk < (2/ak)P(n) for all

n > No. This proves part (b). N