Discrete Mathematics for Computer Science

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 33 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