578
CHAPTER 9 Recurrence Relations
k Cj+I " f(dk+l/dJ+l) + f(dk+l)
dk dkl)
j=0
k+I
-
L C' " f(dk+l/di)
j=0
as required.
Corollary 1.
The solution to the binary search recurrence relation
T(
< IT(n/2)+l forn=2kk>l
I I
for n = 1
is T(n) < log 2 (n + 1).
Proof Let C = 1, d = 2, and f(n) = 1. The theorem gives
k
T(n) <
1 = k + 1
j=0
Since k = log 2 (n), T(n) = 1 log 2 (n).
Corollary 2. The solution to the merge sort recurrence relation
T(n)< 2T(n/2)+n forn=r2k, k>1
-1
for n = 1,
is T(n) < n + n log 2 (n).
Proof Let C = 2, d = 2, and f(n) = n. The theorem gives
k
T(n) < Z2j(n/2dj)
j=0
= (k + 1)n
(k = log 2 (n))
= n + n log 2 (n)
Corollary 3. The solution to the n-bit multiplication recurrence relation
T (n) =3T
(n/2) + mn for n = 2 k, k> 1, m a constant
Im
for n = 1
is T(n) = 3mn1°g2
3 - 2mn.
Proof Let C = 3, d = 2, and f(n) = mn. The theorem gives
k
T(n) = Y 3 3 j • 2J
j=O
= mn y
j=O
(3/2)k+l
1
(3/2) - 1
3k+l _2k+l
mn 2k- 3-2
2