Discrete Mathematics for Computer Science

576 CHAPTER 9 Recurrence Relations

Divide-and-Conquer Recurrence Relations

To focus attention on the kinds of recurrence relations that represent the divide-and-

conquer algorithms, we have examined three different algorithms. To avoid some of the

detailed analysis that is needed to handle problems of size n for any it, we make a simpli-

fying assumption about the form of the integers for which a divide-and-conquer recur-

rence relation is defined. The divide and conquer algorithms examined are restricted to

those that satisfy a recurrence relation of the form

T(n) ICT(')+-f(n) forn-=dk(k>0)

T f(1) for n = 1 (k = 0)

where C is a constant and k > 0. A solution for this recurrence would only give an exact or

closed-form answer for the case that n = dk for some k. This is often enough information

about the recurrence to determine the complexity for all n. In the case of the functions that

are normally encountered, it is reasonable to assume that if m lies in the interval

dk < m < dk+l

then

T(dk) <T(m) < T(dk+1)

One certainly expects that T (dk+l) is an upper bound for T (m) whenever m < dk+l, since

solving a problem for m objects normally should not be more complicated than solving the

same problem for a larger number of elements. With the aid of this assumption about n, the

computations are considerably simplified. This simplification allows removal of the floor

and ceiling functions from the recurrence used to describe the complexity of the binary

search and merge sort procedures, since [n/d] = Ln/dj = n/d when n = dk for some

k >0.

After solving the divide-and-conquer recurrence in terms of the parameters C, n, and

the function f, this solution will lead to a description of the behavior of the algorithms

examined earlier:

SBinary search C=I1, d =2, f (n)=lI

Merge sort C =2, d =2, f (n)= n

n-Bit multiplication C = 3, d = 2, f(n) = cn, c a constant

The method of solution is the same as that used with the first-order recurrence

relations-that is, use back substitution until a pattern is recognized and then a proof by

induction that this pattern leads to the solution.