Discrete Mathematics for Computer Science

294 CHAPTER 5 Analysis of Algorithms

Proof. (a) We first establish an inequality involving nk and then define No and c:

nk < nC c= [k and

n <21 l1 [log 2 (n)] then

nk < 2 c1

Choose No = cl. If n > No, then

nk < 2 No < 2 n

(b) Suppose 2' E 0 (nk) for some natural number k. By part (a), nk+l E 0(2n). It follows

by the transitivity of asymptotic domination (Theorem 3) that nk+l E O(nk), contra-

dicting Theorem 5. U

Hand-checking values in the proof of Theorem 7(a) will make the reader suspect (cor-

rectly) that this constant is much larger than needed. It does, however, make the proof

easier to establish.

A more complete description of the general relation between exponential functions is

proven in Theorem 8. Examples of this result include 7r' E 0(4n), but 4' 0 0(7r').

Theorem 8. Let n E N.

(a) Let a and b be real numbers such that I < a < b. Then, a" E 0(bn) and bn 0 0(an).

(b) Let a, b, and c be real numbers, with 0 < a < b and c > 1. Then, can E O(cbn) and

Cbn _ o(Can).

Proof. This proof is left as an exercise for the reader. U

As another example that will be of use in analyzing sorting algorithms, we can show

that the function F(n) = n grows faster than the function G(n) = ln(n).

Example 5. Let F(n) = n and G(n) = ln(n) be functions from N to R. Then, G E O(F),

but F g O(G), as shown in Figure 5.6.

(^104) x x
x
7.5 x x

Fiue56Fn son x)n G on In o o (sow o)oo.

2.5- x^0 o

X o

0 2 4 6 8 10 12

-2.5-

Figure 5.6 F(n) = n (shown x) and G(n) = In(n) (shown o).

Solution. First, show that ln(n) E O(n). For all n E N, we have n < 2". Since e > 1, by

facts (c) and (g) cited previously about logarithmic functions, tn(n) < n ln(2). This estab-

lishes the result with No = 1 and c = ln(2). (We set No = 1, because ln(O) is undefined.)