Mathematics for Computer Science

Chapter 21 Recurrences886

where:

1.x 0 is large enough so thatTis well-defined,

2.a 1 ;:::;akare positive constants,

3.b 1 ;:::;bkare constants between 0 and 1,

4.g.x/is a nonnegative function such thatjg^0 .x/jis bounded by a polynomial,

5.jhi.x/jDO.x=log^2 x/.

Then

T.x/D‚



xp



1 C

Zx

1

g.u/

upC^1

du



wherepsatisfies
Xk

iD 1

aibipD1:

The Akra-Bazzi theorem can be proved using a complicated induction argument,
though we won’t do that here. But let’s at least go over the statement of the theorem.
All the recurrences we’ve considered were defined over the integers, and that is
the common case. But the Akra-Bazzi theorem applies more generally to functions
defined over the real numbers.
The Akra-Bazzi formula is lifted directed from the theorem statement, except
that the recurrence in the theorem includes extra functions,hi. These functions
extend the theorem to address floors, ceilings, and other small adjustments to the
sizes of subproblems. The trick is illustrated by this combination of parameters

a 1 D 1 b 1 D1=2 h 1 .x/D

lx

2

m



x

2

a 2 D 1 b 2 D1=2 h 2 .x/D

jx

2

k

x

2

g.x/Dx 1

which corresponds the recurrence

T.x/D 1 
T

x

2

C

lx

2

m

x

2



C
T

x

2

C

jx

2

k

x

2



Cx 1

DT

lx

2

m

CT

jx

2

k

Cx1:

This is the rigorously correct Merge Sort recurrence valid for all input sizes,
complete with floor and ceiling operators. In this case, the functionsh 1 .x/and