Divide-and-Conquer Recurrence Relations
577
Theorem 1. (Solution of Divide-and-Conquer Recurrences) The solution of
T
=CT(n/d)+f(n) forn~dk, k> 1
If( 1 )
forn = 1
is the function T(n) =
k C'f(n/dj).
Motivation for Proof.
(Base step) For k = 0,
E- C f(n/dj) = f(1) = T(1)
j=0
(Inductive step) Now, suppose that the formula holds for m > 0. That is,
m
T(m) = 5Cj
f(n/dj)
j=0
Now, prove that T (m + 1) is also given by this expression. In this case, prove that
m+1
T(m + 1) =
CcJ f(dm+l/dj)
j=0
Back substitutions will give
T(n) = CT(n/d) + f(n)
= C{CT(n/d
2 ) + f(n/d)} + f(n)
= C
2 T(n/d
2 ) + Cf(n/d) + f(n)
= C
2 {CT(n/d
3 ) + f (n/d
2 )} + Cf(n/d) + f(n)
= C
3 • T(n/d
3 ) + C
2 . f(n/d
2 ) + Cf(n/d) + f(n)
The pattern is
k
T(n) =
Cif(n/dj)
j=0
Proof. Now, verify that this is the solution using induction on k where n = dk. For
k = 0,
0
ECi f(1/dj) = f(1) = T(1)
j=0
Now, suppose that the formula holds for m = k where k < 0, and show that it holds for
m = k +1:
T(dk+l) = CT(d k) + f(dk+l)
k
= C YC'.f
(dk/di) + f(dk+l) (Induction hypothesis)
j=0