DESIGN AND ANALYSIS OF ALGORITHM
Unit 3: Solving Recurrences
Department of Information Technology
Department of Information Technology CSPIT
Recurrences
Def.: Recurrence = an equation or inequality that describes a
function in terms of its value on smaller inputs, and one or
more base cases
E.g.: T(n) = T(n-1) + n
Useful for analyzing recurrent algorithms
Methods for solving recurrences
Master Theorem
Substitution method
Recursion tree method
Department of Information Technology CSPIT
Recursion-tree method
• A recursion tree models the costs (time) of a
recursive execution of an algorithm.
• The recursion tree method is good for generating
guesses for the substitution method.
• The recursion-tree method can be unreliable, just like
any method that uses ellipses (…).
• The recursion-tree method promotes intuition,
however.
L2.3
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
L2.4
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
T(n)
L2.5
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
T(n/4) T(n/2)
L2.6
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
T(n/16) T(n/8) T(n/8) T(n/4)
L2.7
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
L2.8
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
n2
(n/4)2 (n/2)2
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
L2.9
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
n2
(n/4)2 (n/2)2 5 2
n
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2
Q(1)
L2.10
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
n2
(n/4)2 (n/2)2 5 2
n
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 2
n
256
…
Q(1)
L2.11
Example of recursion tree
Solve T(n) = T(n/4) + T(n/2) + n2:
n2
n2
(n/4)2 (n/2)2 5 2
n
16
(n/16)2 (n/8)2 (n/8)2 (n/4)2 25 2
n
256
…
Q(1)
Total = 2 2 3
n 1 5
5
5
16 16 16
= Q(n2) geometric series
L2.12
The master method
The master method applies to recurrences of the form
T(n) = a T(n/b) + f (n) ,
where a 1, b > 1, and f is asymptotically positive.
L2.13
Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) … f (n/b) a f (n/b)
f (n/b)
a
h = logbn
f (n/b2) … f (n/b2) a2 f (n/b2)
f (n/b2)
…
#leaves = ah nlogbaT (1)
T (1) = alogbn
= nlogba
L2.14
Three common cases
Compare f (n) with nlogba:
1. f (n) = O(nlogba – e) for some constant e > 0.
• f (n) grows polynomially slower than nlogba
(by an ne factor).
Solution: T(n) = Q(nlogba) .
L2.15
Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) … f (n/b) a f (n/b)
f (n/b)
a
h = logbn
f (n/b2) … f (n/b2) a2 f (n/b2)
f (n/b2)
CASE 1: The weight increases
…
geometrically from the root to nlogbaT (1)
T (1) the leaves. The leaves hold a
constant fraction of the total Q(nlogba)
weight.
L2.16
Three common cases
Compare f (n) with nlogba:
2. f (n) = Q(nlogba lgkn) for some constant k 0.
• f (n) and nlogba grow at similar rates.
Solution: T(n) = Q(nlogba lgk+1n) .
L2.17
Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) … f (n/b) a f (n/b)
f (n/b)
a
h = logbn
f (n/b2) … f (n/b2) a2 f (n/b2)
f (n/b2)
…
CASE 2: (k = 0) The
nlogbaT (1)
T (1)
weight is approximately
the same on each of the
logbn levels. Q(nlogbalg n)
L2.18
Three common cases (cont.)
Compare f (n) with nlogba:
3. f (n) = W(nlogba + e) for some constant e > 0.
• f (n) grows polynomially faster than nlogba (by
an ne factor),
and f (n) satisfies the regularity condition that
a f (n/b) c f (n) for some constant c < 1.
Solution: T(n) = Q( f (n)) .
L2.19
Idea of master theorem
Recursion tree:
f (n) f (n)
a
f (n/b) … f (n/b) a f (n/b)
f (n/b)
a
h = logbn
f (n/b2) … f (n/b2) a2 f (n/b2)
f (n/b2)
CASE 3: The weight decreases
…
geometrically from the root to nlogbaT (1)
T (1) the leaves. The root holds a
constant fraction of the total Q( f (n))
weight.
L2.20
The Master Theorem
Given: a divide and conquer algorithm
An algorithm that divides the problem of size n into a
subproblems, each of size n/b
Let the cost of each stage (i.e., the work to divide the
problem + combine solved subproblems) be described
by the function f(n)
Then, the Master Theorem gives us a cookbook
for the algorithm’s running time
The Master Theorem
if T(n) = aT(n/b) + f(n) then
Q n
logb a
f ( n ) O n
logb a e
e 0
T (n) Q n logb a
log n f (n) Q n
logb a
c 1
Q f (n)
f (n) W n logb a e AND
af (n / b) cf (n) for large n
Department of Information Technology CSPIT
24
Properties
Transitivity
f(n) = Q(g(n)) & g(n) = Q(h(n)) f(n) = Q(h(n))
f(n) = O(g(n)) & g(n) = O(h(n)) f(n) = O(h(n))
f(n) = W(g(n)) & g(n) = W(h(n)) f(n) = W(h(n))
f(n) = o (g(n)) & g(n) = o (h(n)) f(n) = o (h(n))
f(n) = w(g(n)) & g(n) = w(h(n)) f(n) = w(h(n))
Reflexivity
f(n) = Q(f(n))
f(n) = O(f(n))
f(n) = W(f(n))
Department of Information Technology CSPIT
Properties
Symmetry
f(n) = Q(g(n)) iff g(n) = Q(f(n))
Complementarity
f(n) = O(g(n)) iff g(n) = W(f(n))
f(n) = o(g(n)) iff g(n) = w((f(n))
Department of Information Technology CSPIT
