418
Relations, Functions, and Matrices
3 A more complicated master theorem gives similar results for the case of Equation (2).
This type of recurrence relation arises in the analysis of an algorithm that splits
the input in half and operates recursively on one or more of the halves. A more
general divide-and-conquer recurrence relation divides the input into subproblems
that are each of size n∙b and then operates recursively on a of the subproblems.
Each subproblem requires S(n∙b) work with g(n) representing the work required
to divide into subproblems or recombine the results of solving the subproblems.
Such a recurrence relation would have the form
S(n) = aS a
n
b
b + g(n) for n ≥ 2, n = b
m
(2)
We assume that n is an integral power of b so that dividing n by b over and over
always results in an integer.
A result called the master theorem gives us order-of-magnitude results via a
cookbook formula for the case when g(n) = n
c
. Thus, assume the recurrence relations of interest look like this:
3
S(n) = aS a
n
b
b + n
c
for n ≥ 2, n = b
m
(3)
theoRem MaSteR tHeoReM
Consider the recurrence relation
S(1) ≥ 0
S(n) = aS a
n
b
b + n
c
for n ≥ 2
where n = b
m
, a, and b are integers, a ≥ 1, b > 1, and c is a nonnegative real
number. Then
1. if a < b
c
S(n) = Θ(n
c
)
2. if a = b
c
S(n) = Θ(n
c
log n)
3. if a > b
c
S(n) = Θ(n
log b a
)
example 46
A recurrence relation of the form
S(n) = 4S a
n
5
b + n
3
for n ≥ 2, n = 5
m
matches the form of the recurrence relation shown in the master theorem where
a = 4, b = 5, and c = 3. Because 4 < 5
3
, Case 1 applies and the master theorem
says that S(n) = Θ(n
3
).