Divide-and-Conquer Recurrence Relations 577Theorem 1. (Solution of Divide-and-Conquer Recurrences) The solution ofT =CT(n/d)+f(n) forn~dk, k>^1
If( 1 ) forn = 1is 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,
mT(m) = 5Cj f(n/dj)
j=0Now, prove that T (m + 1) is also given by this expression. In this case, prove that
m+1T(m + 1) = CcJ f(dm+l/dj)
j=0Back 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=0Proof. 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=0Now, 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