SOLVING RECURRENCE
Tanjina Helaly
RECURRENCE
Recurrences are a major tool for analysis of
algorithms
Divide and Conquer algorithms which are
analyzable by recurrences.
RECURRENCES AND RUNNING TIME
An equation or inequality that describes a
function in terms of its value on smaller inputs.
T(n) = T(n-1) + n
Recurrences arise when an algorithm contains
recursive calls to itself
What is the actual running time of the
algorithm?
Need to solve the recurrence
Find an explicit formula of the expression
Bound the recurrence by an expression that involves n
EXAMPLE RECURRENCES
T(n) = T(n-1) + n Θ(n2)
Recursive algorithm that loops through the input to
eliminate one item
T(n) = T(n/2) + c Θ(lgn)
Recursive algorithm that halves the input in one step
T(n) = T(n/2) + n Θ(n)
Recursive algorithm that halves the input but must
examine every item in the input
T(n) = 2T(n/2) + 1 Θ(n)
Recursive algorithm that splits the input into 2
halves and does a constant amount of other work
4
METHODS FOR SOLVING RECURRENCES
Iteration method
Substitution method
Recursion tree method
Master method
5
ITERATION METHOD
THE ITERATION METHOD
Convert the recurrence into a summation and try
to bound it using known series
Iterate the recurrence until the initial condition is
reached.
Use back-substitution to express the recurrence in
terms of n and the initial (boundary) condition.
7
THE ITERATION METHOD
T(n) = c + T(n/2)
T(n) = c + T(n/2) = c+T(n/21)
= c + c + T(n/4) = c+c+T(n/22) T(n/2) = c + T(n/4)
= c + c + c + T(n/8) = c+c+c+T(n/23)
= …… T(n/4) = c + T(n/8)
= c+c+…+c+T(n/2k)
Assume n = 2k => k = log n
So, T(n) = c + c + … + c + T(1)
k times
= clgn + T(1)
= Θ(lgn) [T(1) = constant]
ITERATION METHOD – EXAMPLE
T(n) = n + 2T(n/2)
T(n) = n + 2T(n/2)
T(n/2) = n/2 + 2T(n/4)
= n + 2(n/2 + 2T(n/4))
= n + n + 4T(n/4)
= n + n + 4(n/4 + 2T(n/8))
= n + n + n + 8T(n/8)
Assume 2 k
= in + 2iT(n/2i) n/2k = 1 => k = log n
= kn + 2kT(1)
= nlgn + nT(1) = Θ(nlgn) [T(1) = constant]
SUBSTITUTION METHOD
THE SUBSTITUTION METHOD
Guess a bound/solution
Use mathematical induction to prove our guess
correct.
SUBSTITUTION METHOD
Guess a solution
T(n) = O(g(n))
Induction goal: apply the definition of the asymptotic
notation
T(n) ≤ d g(n), for some d > 0 and n ≥ n0 (strong induction)
Induction hypothesis: T(k) ≤ d g(k) for all k < n
Prove the induction goal
Use the induction hypothesis to find some values of
the constants d and n0 for which the induction goal
holds
12
SUBSTITUTION METHOD –
EXAMPLE(BINARY SEARCH)
T(n) = c + T(n/2)
Guess: T(n) = O(lgn)
Induction goal: T(n) ≤ d lgn, for some d and n ≥ n0
Induction hypothesis: T(n/2) ≤ d lg(n/2)
Proof of induction goal:
T(n) = T(n/2) + c ≤ d lg(n/2) + c
= d lgn – d + c ≤ d lgn
if: – d + c ≤ 0, d ≥ c
SUBSTITUTION METHOD – EXAMPLE 2
T(n) = T(n-1) + n
Guess: T(n) = O(n2)
Induction goal: T(n) ≤ c n2, for some c and n ≥ n0
Induction hypothesis: T(n-1) ≤ c(n-1)2 for all k < n
Proof of induction goal:
T(n) = T(n-1) + n ≤ c (n-1)2 + n
= cn2 – (2cn – c - n) ≤ cn2
if: 2cn – c – n ≥ 0 c ≥ n/(2n-1) c ≥ 1/(2 – 1/n)
For n ≥ 1 2 – 1/n ≥ 1 any c ≥ 1 will work
SUBSTITUTION METHOD – EXAMPLE 3
T(n) = 2T(n/2) + n
Guess: T(n) = O(nlgn)
Induction goal: T(n) ≤ cn lgn, for some c and n ≥ n0
Induction hypothesis: T(n/2) ≤ cn/2 lg(n/2)
Proof of induction goal:
T(n) = 2T(n/2) + n ≤ 2c (n/2)lg(n/2) + n
= cn lgn – cn + n ≤ cn lgn
if: - cn + n ≤ 0 c ≥ 1
RECURSION TREE METHOD
RECURSION TREE METHOD
A recursion tree models the costs (time) of a
recursive execution of an algorithm.
Convert the recurrence into a tree:
Each node represents the cost incurred at
various levels of recursion
Sum up the costs of all levels
The recursion tree method is good for generating
guesses for the substitution method.
EXAMPLE – MERGE SORT
Time Complexity, T(n) = 2T(n/2) + cn
T(n)
EXAMPLE – MERGE SORT CONT…
T(n) = 2T(n/2) + cn
cn
T(n/2) T(n/2)
EXAMPLE – MERGE SORT CONT…
T(n) = 2T(n/2) + cn
cn T(n/2) = 2T(n/4) +cn/2
cn/2 cn/2
T(n/4) T(n/4) T(n/4) T(n/4)
EXAMPLE – MERGE SORT CONT…
T(n) = 2T(n/2) + cn
cn
cn/2 cn/2
cn/4 cn/4 cn/4 cn/4
Height = log n
# of level=log n+1
……..
c c c c c c c c
n leaves
EXAMPLE – MERGE SORT CONT…
T(n) = 2T(n/2) + cn Cost for each node = cn/2i .
Cost at each level = 2i * cn/2i
i=0 cn/2i = cn
i=1 cn/2i cn/2i
i=2 cn/2i cn/2i cn/2i cn/2i
Height = log n
# of level=log n+1
……..
c c c c c c c c At last level, n/2i = 1
So, 2i = n
n leaves => i = log n
EXAMPLE – MERGE SORT CONT…
T(n) = 2T(n/2) + c Cost
-----
cn cn
cn/2 cn/2 cn
cn/4 cn/4 cn/4 cn/4 cn
Height = log n
# of level=log n+1
……..
c c c c c c c c cn
n leaves Total cost =(logn +1) * cn
= cnlogn + cn
= θ(n log n)
RECURSION TREE – EXAMPLE 2
T(n) = 2T(n/2) + cn2
RECURSION TREE – EXAMPLE 2
RECURSION TREE – EXAMPLE 3
RECURSION TREE – EXAMPLE 3
T(n) = T(n/3) + T(2n/3) + n.
So, total cost = Total cost =(log3/2 n +1) * n
= nlog3/2 n + n
= nlogn/log(3/2) +n
= θ(n log n)
RECURSION TREE – EXAMPLE 4
T(n) = 3T(n/4) + cn2
RECURSION TREE – EXAMPLE 4 CONT…
T(n) = 3T(n/4) + cn2
ANOTHER EXAMPLE – CONT…
RECURSION TREE – EXAMPLE 4 CONT…
# of node at each step 3i
# of node at last step 3log n 4
as i log n
4
n log 4 3
As we assumed T(1) is constant
Cost at leaf level n T (1)
log 3 4
(n log 4 3
)
RECURSION TREE – EXAMPLE 4 CONT…
3 3 3
T (n) cn cn ( ) cn ..... ( )
2 2 2 2 log 4 n 1
cn (n
2 log 4 3
)
16 16 16
3
log 4 n 1
( ) cn (n ) i 2 log 4 3
i 0
16
3
( ) cn (n ) i 2 log 4 3
i 0
16
1
cn (n ) 2 log 4 3
1 3 / 16
16
cn (n ) 2 log 4 3
13
O( n ) 2
RECURSION TREE – EXAMPLE 4 CONT…
Or solve the following way
3 2 3 2 2 3 log4 n1 2
T (n) cn cn ( ) cn ..... ( )
2
cn (nlog4 3 )
16 16 16
log 4 n 1
3
( )i cn 2 (nlog4 3 )
i 0 16
1 (3 / 16)log n 2
cn (nlog4 3 )
1 3 / 16
16 2
cn (nlog4 3 ) [as n , (3 / 16)log n 0]
13
(n 2 )
MASTER’S METHOD
MASTER’S METHOD
“Cookbook” for solving recurrences of the form:
n
T (n) aT f (n)
b
where, a ≥ 1, b > 1, and f(n) > 0
Idea: compare f(n) with nlogba
f(n) is asymptotically smaller or larger than
nlogba by a polynomial factor n
f(n) is asymptotically equal with nlogba
MASTER’S METHOD
“Cookbook” for solving recurrences of the form:
n
T (n) aT f (n)
b
where, a ≥ 1, b > 1, and f(n) > 0
Case 1: if f(n) = O(nlogba -) for some > 0, then: T(n) = (nlogba)
Case 2: if f(n) = (nlogba), then: T(n) = (nlogba lgn)
Case 3: if f(n) = (nlogba +) for some > 0, and if
af(n/b) ≤ cf(n) for some c < 1 and all sufficiently large n,
then:
regularity condition T(n) = (f(n))
WHY NLOGBA?
n
T (n) aT
b
n
a 2T 2
b
n
a 3T 3
b
n
T (n) a iT i i
b
Assume n = bk k = logbn
At the end of iteration i = k:
i
b
T (n) a T i a logb nT (1) a logb n nlogb a
logb n
b
MASTER’S METHOD – EXAMPLE 1
T(n) = 2T(n/2) + n
a = 2, b = 2, log22 = 1
Compare g(n) =nlog22 =n with f(n) = n
f(n) = (n) Case 2
T(n) = (nlgn)
MASTER’S METHOD – EXAMPLE 2
T(n) = 2T(n/2) + n2
a = 2, b = 2, log22 = 1
Compare n with f(n) = n2
f(n) = (n1+) Case 3 verify regularity cond.
a f(n/b) ≤ c f(n)
2 n2/4 ≤ c n2 c = ½ is a solution (c<1)
T(n) = (n2)
MASTER’S METHOD – EXAMPLE 3
REFERENCE
Chapter 4 (Cormen)
https://www.cse.unr.edu/~bebis/CS477/Lect/Recurr
ences.ppt
https://courses.csail.mit.edu/6.046/spring04/lectures
/l2.ppt
https://www.cs.cornell.edu/courses/cs3110/2012sp/lectu
res/lec20-master/lec20.html
