Notes on Better Master Theorems
for
DivideandConquer Recurrences
Intro duction
Divideandconquer recurrences are ubiquitous known for solving recurrences such as
in
the
analysis of algorithms
Many metho ds are
Tom
Mathematics Laboratory for
Leighton
Department and
Computer Science Massachusetts Institute of Technology
Cambridge Massachusetts
Octob er
Abstract
Techniques
Computer Science
known as the Master Metho d Recently Akra and Bazzi discovered a surprisingly elegant generalization of the Master Metho d that yields a very simple formula for solving most divide andconquer recurrence s In these notes we provide a simple inductive pro of of the AkraBazzi result and we extend the result to handle variations of divideandconquer recurrences that commonly arise in practice
for solving divideandconquer recurrences are routinely
students each year The dominant approach to solving such recurrence s is
Tn
T dne On if n
but p erhaps the most widely taught approach is the Master Metho d that is describ ed in the seminal algorithms text by Cormen Leiserson and Rivest
The Master Metho d is fairly p owerful and results in a closed form solution for divideandconquer recurrences with a sp ecial but commonlyo ccurring form Recently Akra and Bazzi discovered a far more general solution to divideandconquer recurrences The AkraBazzi analysis is based on a sp ecial functional transform that they call the order transform
In these notes we give a simple inductive pro of of the AkraBazzi result that is suitable for use in an undergraduate algorithms or discrete math class We also show that the AkraBazzi result holds for a more general class of recurrences that commonly arise in practice and that are often considered to b e dicult to solve
if n
taught to
thousands of
The AkraBazzi Solution
We b egin with of the form
where
a
simple
inductive pro of of the
k
i aiT bix gx
number for which i aibi Then
Z x
gu
du up
Tx P
for x x
for x x
AkraBazzi result The result
holds
for recurrences
xisarealnumber
xisaconstantsuchthatxbiandxbiforik
aiisaconstantforik
biisaconstantforik
k is a constant and
gx is a nonnegative function that satises the polynomialgrowth condition specied below
Denition We say that g x satises the polynomialgrowth condition if there exist positive con stants c c such that for all x for all i k and for all u bix x
cg x g u cg x
Remark If jg xj is upp er b ounded by a p olynomial in x then g x satises the p olynomial growth condition For example g x x log x satises the p olynomialgrowth condition for any constants R
Theorem PGiven a recurrence of the form specied in Equation let p be the unique real kp
p Tx x
Examples
If
If
If
If
T x T x T x T x T x
T x T x x log x then
p
and T x x log x
T x T x x log x then p and T x x log log x
T x log x then p and T x log x
T x x then p and T x log xx
If
These conditions are somewhat less restrictive than those of
T x x then p and T x x
The pro of of Theorem makes use of the following simple lemma from calculus
Lemma
there are positive
Proof
From the
p olynomiaZlgrowth
bi x
condition we know that
If g x is a nonnegative function that satises the polynomialgrowth condition then constants c c such that Zfor i k and al l x
xp
x g u
up
du xpx b x i
c g x
minfb xp xp g i
x g u
c gx xp du c gx up
where we
dene c
to b e
a constant
for
which
bi x
bi c
c g x
g x
min f bpg i
c bi c
minf bp g i
for i k Similarly
Z
bi x
where we
dene c
constant
cg x
for which
xp
to b e a
du xpx b x i
maxfb
xp xp g
x
g u up
cg x
bi c
maxf bpg i
g x
i
c bi c
maxf bpg i
for i k
We will use induction
into intervals I x and Ij x j x j for j
to
prove Theorem and so it will
b e
helpful
to partition the
domain
of x
By the denition of x we know that if x Ij for some j then for i k
bix Ij for
some j j This is because b x b x j b x and because b x b x j iiiii
x j bix x j As a consequence we know that the value of T in any interval after x dep ends only on the values of T in prior intervals
Proof of Theorem We rst show that there is a p ositive constant
c such that for all x x
Zxgu Txc xp du
up
on the interval Ij containing x when x x provided that we
The inductive step is argued as follows Xk
The
the fact that T x
case when j follows from small enough
pro of is by induction
The base cho ose c
T x
cxp
i Xk
i
a c b xp ii
Zbixgu
ai T bi x g x
up
du gx
by induction
by Lemma
c xp
c xp
cxp
Xk Zxgu Zxgu aibpi p du p du
i u bixu
Xk Zxgu c
gx
aibp i
up
du gx xp
gx
Z
i
x g u c
du gx gx
Zup xp
that c c
provided
The pro of that there is a
p ositive constant c
Txc xp
such that
for all
x
x g u
up
cxp
du gx c c
Z
gx
x g u up
du
x
Zxgu
du up
is nearly identical We need only insure that c is chosen large enough so that the base case is
satised and so
as claimed
Remark If
do es not necessarily hold if g x do es not satisfy the p olynomialgrowth condition
that c c As a consequence we can conclude that
Zxgu
p
Tx x du
up
g x grows faster than any p olynomial in x then T x g x Hence Theorem
Variations
Although the class of recurrences analyized in Section is quite broad recurrences that arise in practice often dier in small ways from the class sp ecied in Equation For example in algorithm design recurrences of the form
are common
Generally sp eaking the inclusion
Xk
T x ai T dbi xe g x
i
of o ors and ceilings in a recurrence do es not signicantly change
for all
where
x x
tend to b e fairly tedious and of variations which includes ceilings and we show that the variations in this class do not aect the solution of the
the nature
sp ecialized
o ors and
recurrence up to constant factors In particular we show that the solution of Theorem holds
of the solution eg see but the pro ofs of this fact in nature In what follows we describ e a general class
recurrences
of the form
ai
bi
k and g x all satisfy the conditions sp ecied in Section
Tx P k
for x x
for x x
i aiT bix hix gx
there is some constant for which jh xj xlog x for i k whenever x x i
there exist p ositive constants c and c such that for all x for all i k and for all
u bix hi x x
cg x g u c g x
and
x is chosen to be a large enough constant so that for any i k and any x x
A ap
bi log x log b x x log x i
logx
pA
b
bi log x log b x x log x ilogx
c
logx
d
log x
Such a constant value of x can b e shown to exist using standard Taylor series expansions and asymptotic analysis
For example we might cho ose hi so that
hi x dbi xe bix
thereby extending Theorem to handle ceiling functions In this case jh xj We can also use pi
much larger functions however For example we could set h x x or h x xlog x for ii
x
To analyze the more general recurrence we will need the following analogue of Lemma
There are positive constants cZ c such that for i k and all x
x
Lemma
Proof of the
TheoremP Given a recurrence of the form specied in Equation let p be the unique real number kp
Zxgu
p
Tx x du
up
Proof The pro of is very similar to that of Theorem The main dierence is that we use a slightly stronger inductive hyp othesis In particular we b egin by showing that there is a p ositive constant c
c gx xp
up
bi xhi x
g u
pro of is identical to that for Lemma except that we use constraint ab ove in place
The
p olynomialgrowth condition of Section
for which i ai bi Then
du c gx
such that for all x x
Zxgu Txc xp du
fact that T x when x x provided that c
is chosen to b e a small enough constant
log x up
The pro of is by induction on the interval Ij containing x The base case when j follows from the
The inductive step is argued as follows Xk
T x
i
ai T bix hi x g x
Xk
iii
log bi x hi x
a c b x h xp
i
Z bi xhi x g u
p du g x
by induction
u Xkp A
abpcxp ii x
i
bi log x log bix log x
ZxZx
p u
bi xhi x
u
g u
g u
du
Xk Zxguc
aibpcxp
i
Zxgu
cxp
up
p du gx
by the
bounds on h
cxp
log x
x gu
The pro of of the
case we
show by
induction that
there is a
positive
constant
c such
x x
i logx
du gx up xp
gx
by constraint a on
Zxgu c
cxp
log x up
du
gx xp
gx
by upp er b ound
x
du up
x and Lemma
du gxc c
gx
log x Z
log x
provided that c c
constraint c on
is quite similar In this
that for all
Txc xp
Zxgu
du log x up
The base case is as b efore The inductive step is argued as
Xk
T x ai T bix hi x g x
follows
i Xk
a c b x h xp iii
log bi x hi x
i
Z bi xhi x g u
p du g x
by induction
u Xkp A
abpcxp ii
i
bi log x log b x x
i
aibpcxp
i
p du gx
by the
bounds
on h
log x ZxZx
p u
bi xhi x
u
g u
g u
du
Xk Zxguc
i logx
du gx up xp
gx
by constraint b on
Zxgu c
du
cxp
gx xp
x and Lemma
gx
gx
Zxgu
T x xp du up
log x up
du gxc c
Zxgu
cxp
up
log x
log x Z x gu
cxp du
log x up
provided that c c Hence we can conclude that
as desired
by constraint d on x
Remark It is worth noting that the x log x limit on the size of jh xj is nearly tight since i
the solution
of the
recurrence Tx
T x x
log x
for x x for x x
is T x x log x which is dierent than the solution of x for the recurrence without the x log x term
References
M Akra and L Bazzi On the solution of linear recurrence equations To app ear
Thomas H Cormen Charles E Leierson and Ronald L Rivest Introduction to Algorithms The MIT Press Cambridge Massachusetts