Mathematics for Computer Science

21.4. Divide-and-Conquer Recurrences 883

Merge Sort is an example of a divide-and-conquer algorithm: it divides the in-
put, “conquers” the pieces, and combines the results. Analysis of such algorithms
commonly leads todivide-and-conquerrecurrences, which have this form:

T.n/D

Xk

iD 1

aiT.bin/Cg.n/

Herea 1 ;:::akare positive constants,b 1 ;:::;bkare constants between 0 and 1,
andg.n/is a nonnegative function. For example, settinga 1 D 2 ,b 1 D1=2, and
g.n/Dn 1 gives the Merge Sort recurrence.

21.4.1 The Akra-Bazzi Formula

The solution to virtually all divide and conquer solutions is given by the amazing
Akra-Bazzi formula. Quite simply, the asymptotic solution to the general divide-
and-conquer recurrence

T.n/D

Xk

iD 1

aiT.bin/Cg.n/

is

T.n/D‚



np



1 C

Zn

1

g.u/

upC^1

du



(21.2)

wherepsatisfies
Xk

iD 1

aibpi D1: (21.3)

A rarely-troublesome requirement is that the functiong.n/must not grow or
oscillate too quickly. Specifically,jg^0 .n/jmust be bounded by some polynomial.
So, for example, the Akra-Bazzi formula is valid wheng.n/Dx^2 logn, but not
wheng.n/D 2 n.
Let’s solve the Merge Sort recurrence again, using the Akra-Bazzi formula in-
stead of plug-and-chug. First, we find the valuepthat satisfies

2 
.1=2/pD1: