194
Recursion, Recurrence Relations, and Analysis of Algorithms
where c is a constant and g can be an expression involving n. It’s convenient to
look only at values of n that are powers of 2 because then cutting n in half over
and over always results in an integer. As we will see in the next section, this is not
a significant restriction.
To solve a divide-and-conquer recurrence relation, we go back to the expand,
guess, and verify approach. Also, the solution will involve the logarithm function;
for a review of the logarithm function and its properties, see Appendix C.
example 24
Solve the recurrence relation
C(n) = 1 + C a
n
2
b for n ≥ 2, n = 2
m
subject to the basis step
C(1) = 1
Expanding, we get
C(n) = 1 + C a
n
2
b
= 1 + a1 + Ca
n
4
b b
= 1 + 1 + a1 + Ca
n
8
b b
(
and the general term seems to be
C(n) = k + C a
n
2
k b
The process stops when n/2
k
= 1 or 2
k
= n, which means k = log 2 n. (We’ll omit
the base 2 notation from now on—log n will mean log 2 n. See Appendix C for a
brief discussion of logarithms.) Then
C(n) = log n + C(l) = 1 + log n
Now we will use induction to verify that C(n) = 1 + log n for all n ≥ 1,
n = 2
m
. This is a somewhat different form of induction, because the only values of
interest are powers of 2. We still take 1 as the basis step for the induction, but then
we prove that if our statement is true for a value k, it is true for 2k. The statement
will then be true for 1, 2, 4, 8, … , that is, for all nonnegative integer powers of 2,
which is just what we want.
For the base case,
C(1) = 1 + log 1 = 1 + 0 = 1, true