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), contradicting Theorem 5.
U
Hand-checking values in the proof of Theorem 7(a) will make the reader suspect (correctly) 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 o
In
o (sow o)oo.
2.5x
0 o
X
o
0 2
4
6
8
10
12
-2.5Figure 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 establishes the result with No = 1 and c = ln(2). (We set No = 1, because ln(O) is undefined.)
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), contradicting Theorem 5.
U
Hand-checking values in the proof of Theorem 7(a) will make the reader suspect (correctly) 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 o
In
o (sow o)oo.
2.5x
0 o
X
o
0 2
4
6
8
10
12
-2.5Figure 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 establishes the result with No = 1 and c = ln(2). (We set No = 1, because ln(O) is undefined.)