196
Recursion, Recurrence Relations, and Analysis of Algorithms
Making this substitution in (19) results in
T(m) = c
m
T(0) + ∙
m
i=1
c
m−i
g(2
i
)
(20)
Now reversing the substitution T(m) = S(2
m
), (20) becomes
S(2
m
) = c
m
S(2
0
) + ∙
m
i=1
c
m−i
g(2
i
)
Finally, letting 2
m
= n or m = log n, we get
S(n) = c
log n
S(1) + ∙
log n
i=1
c
(log n)−i
g(2
i
)
(21)
Equation (21) thus represents the solution for the recurrence relation (16). As
before, to use this general solution you need only match your recurrence relation
to (16) to determine c and g(n), then substitute into Equation (21). Again as before, g(n), gives a recipe for what to do with an argument n; in Equation (21), the
argument is 2
i
. If you can evaluate the resulting summation, you will then have a
closed-form solution. Table 3.5 outlines the solution steps.
remInDer
In the summation part
of the general solution
formula, c is raised to the
(log n) − i power, not
(log n) − 1
table 3.5
to Solve recurrence relations of the Form S(n) ∙ cS a
n
2
b ∙ g(n) for n # 2,
n ∙ 2
m
Subject to Initial condition S(1)
1. Match your recurrence relation to the form
S(n) = cS a
n
2
b + g(n)
to find c and g(n).
2. Use c, g(n) and S(1) in the formula
S(n) = c
log n
S(1) + ∙
log n
i=1
c
(log n)−i
g(2
i
)
3. Evaluate the resulting summation to get the final expression.
example 25
The recurrence relation
C(1) = 1
C(n) = 1 + C a
n
2
b for n ≥ 2, n = 2
m
matches Equation (16), with c = 1 and g(n) = 1. Because g(n) = 1, the g function
evaluates to 1 no matter what the argument is. The solution, according to formula
(21), is
C(n) = 1
log n
C(1) + ∙
log n
i=1
1
(log n)−i
(1)
= 1 + (log n)(1) = 1 + log n
which agrees with our previous result from Example 24.