0% found this document useful (0 votes)
39 views

Recurrences: SE 328 Algorithms and Optimization Methods

This document summarizes three methods for solving recurrence relations: substitution method, recursion-tree method, and master method. The substitution method involves guessing a solution and proving it using induction. The recursion-tree method converts a recurrence into a tree to determine costs at each level. The master method provides a general solution for recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

skj djk
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
39 views

Recurrences: SE 328 Algorithms and Optimization Methods

This document summarizes three methods for solving recurrence relations: substitution method, recursion-tree method, and master method. The substitution method involves guessing a solution and proving it using induction. The recursion-tree method converts a recurrence into a tree to determine costs at each level. The master method provides a general solution for recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

skj djk
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 28

LECTURE 4:

Recurrences

SE 328 Algorithms and Optimization Methods


Based on
Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms“,
The MIT Press, 2009
Overview
◼ Running time of a recursive algorithm is described by a
recurrence equation/inequality
◼ Recurrence is an equation (or inequality) that describes a
function in terms of its value on smaller inputs

𝜃 1 if 𝑛 = 1
◼ 𝑇(𝑛) = 2T(𝑛Τ2) + 𝜃(𝑛) if 𝑛 > 1

Solution: 𝑇(𝑛) = 𝜃(𝑛𝑙𝑔𝑛)


Overview
◼ Three methods for solving recurrences:
❑ Substitution method: Guess a bound then show your guess is
correct by induction
❑ Recursion-tree method: Convert recurrence into a tree whose
nodes represents the costs incurred at various levels of the
recursion
❑ Master method: General solution for
𝑇 𝑛 = 𝑎𝑇 𝑛Τ𝑏 + 𝑓(𝑛)
where 𝑎 ≥ 1, 𝑏 > 1 and 𝑓 𝑛 is a given function
◼ In general, we write 𝑇 𝑛 = 2𝑇 𝑛Τ2 + 𝜃 𝑛
Substitution method
◼ Drop constant term part 𝜃(1), since it does not change the
order of growth
◼ Floors & ceilings are also omitted
◼ Steps of substitution method:
❑ Guess the form of the solution (1)
❑ Use induction to find the constants & show the solution works (2)
◼ Applicable when it is easy to guess the form of the answer
◼ Can be used to establish lower or upper bounds
Substitution method
◼ Example: Solve 𝑇 𝑛 = 2𝑇 𝑛Τ2 + 𝑛
◼ Step (1):
Guess the solution as 𝑂(𝑛𝑙𝑔𝑛)
◼ Step (2): (Inductive part)
We must show 𝑇(𝑛) ≤ 𝑐𝑛𝑙𝑔𝑛 holds for suitable const. 𝑐 > 0
Assume that the bound holds for 𝑛Τ2 i.e.
𝑇 𝑛Τ2 ≤ 𝑐 𝑛Τ2 𝑙𝑔( 𝑛Τ2 )
Modify and rewrite the given recurrence by substituting
term 𝑇 𝑛Τ2 by 𝑐 𝑛Τ2 𝑙𝑔( 𝑛Τ2 )
Substitution method
◼ Step (2): (cntd.)
𝑻 𝒏 ≤ 2 𝑐 𝑛Τ2 𝑙 𝑔 𝑛Τ2 + 𝑛
≤ 𝑐𝑛𝑙𝑔 𝑛/2 + 𝑛
= 𝑐𝑛𝑙𝑔𝑛 − 𝑐𝑛𝑙𝑔2 + 𝑛
= 𝑐𝑛𝑙𝑔𝑛 − 𝑐𝑛 + 𝑛
≤ 𝒄𝒏𝒍𝒈𝒏 holds as long as 𝑐 ≥ 1
Step (2): (Base-case part)
𝑇 1 = 1, 𝑇 2 = 2𝑇 1 + 2 = 4, 𝑇 3 = 2𝑇 1 + 3 = 5
We can drop 𝑇(1) by taking 𝑛0 = 2
Substitution method
◼ Step (2): (cntd.)
We must show that 𝑇(𝑛) ≤ 𝑛𝑙𝑔𝑛 for boundary cases, also
So, 𝑇(2) ≤ 𝑐2𝑙𝑔2 and 𝑇(3) ≤ 𝑐3𝑙𝑔3 for some 𝑐 > 0
We have infinitely many such constants 𝑐, if we take 𝑐 ≥ 2
◼ What did we do ?
1. Assuming 𝑇 𝑛Τ2 ≤ 𝑐 𝑛Τ2 𝑙𝑔( 𝑛Τ2 ), we showed that
𝑇(𝑛) ≤ 𝑛𝑙𝑔𝑛 holds (Inductive part)
2. We also showed that 𝑇(𝑛) ≤ 𝑛𝑙𝑔𝑛 holds for 𝑇(2) and
𝑇(3) cases (Base-case part)
Substitution method
◼ How to make good guess ? Experience & creativity
◼ Some heuristics:
1. Given for example, 𝑇 𝑛 = 2𝑇 𝑛Τ2 + 17 + 𝑛,
when 𝑛 is large, 17 does not affect general solution so,
use the same guess: 𝑂(𝑛𝑙𝑔𝑛)
2. Assume loose upper and lower bounds on the
recurrence, then reduce the range, e.g. start with
guesses 𝑇 𝑛 = Ω(𝑛) and 𝑇 𝑛 = 𝑂(𝑛2 ) then squeeze
the range until 𝑇 𝑛 = 𝑂(𝑛𝑙𝑔𝑛) is reached.
Substitution method
◼ Example: Solve 𝑇 𝑛 = 𝑇 𝑛Τ2 + 𝑇 𝑛Τ2 + 1
◼ Step (1):
Guess the solution as 𝑂(𝑛)
◼ Step (2): (Inductive part)
We must show 𝑇(𝑛) ≤ 𝑐𝑛 holds for suitable const. 𝑐 > 0
Assume that the bound holds for 𝑛Τ2 and 𝑛Τ2 i.e.
𝑇 𝑛Τ2 ≤ 𝑐 𝑛Τ2 and 𝑇 𝑛Τ2 ≤ 𝑐 𝑛Τ2
Modify and rewrite the given recurrence by substituting
term 𝑇 𝑛Τ2 by 𝑐 𝑛Τ2 and term 𝑇 𝑛Τ2 by 𝑐 𝑛Τ2
Substitution method
◼ Step (2): (cntd.)
𝑇 𝑛 ≤ 𝑐 𝑛Τ2 + 𝑐 𝑛Τ2 + 1
= 𝑐𝑛 + 1. However, this does not imply 𝑇(𝑛) ≤ 𝑐𝑛
Modify form of the guess as 𝑇 𝑛 ≤ 𝑐𝑛 − 𝑏 where 𝑏 ≥ 0
Then we have, 𝑻 𝒏 ≤ (𝑐 𝑛Τ2 − 𝑏) + 𝑐 𝑛Τ2 − 𝑏 + 1
= 𝑐𝑛 − 2𝑏 + 1
≤ 𝒄𝒏 − 𝒃 as long as 𝑏 ≥ 1
Large enough 𝑐 satisfies both the inequality and its base
case boundary conditions!
Substitution method
◼ Error case example: Solve 𝑇 𝑛 = 2𝑇 𝑛Τ2 + 𝑛
◼ Step (1):
Guess the solution as 𝑂(𝑛)
◼ Step (2): (Inductive part)
We must show 𝑇(𝑛) ≤ 𝑐𝑛 holds for suitable const. 𝑐 > 0
Assume that the bound holds for 𝑛Τ2 i.e.
𝑇 𝑛Τ2 ≤ 𝑐 𝑛Τ2
Modify and rewrite the given recurrence by substituting
𝑇 𝑛Τ2 by 𝑐 𝑛Τ2
Substitution method
◼ Step (2): (cntd.)
𝑻 𝒏 ≤ 2 𝑐 𝑛Τ2 + 𝑛
≤ 𝑐𝑛 + 𝑛 where 𝑐 is constant
= 𝑶(𝒏) Wrong!!!
We have to prove that 𝑇(𝑛) ≤ 𝑐𝑛 but not 𝑇 𝑛 ≤ 𝑐𝑛 + 𝑛
So, change the guess and continue!
Changing variables
◼ Example: Solve 𝑇 𝑛 = 2𝑇 𝑛 + 𝑙𝑔𝑛
Assume 𝑛 returns integer. Set 𝑚 = 𝑙𝑔𝑛. Then,
𝑇 2𝑚 = 2𝑇 2𝑚Τ2 + 𝑚
Rename 𝑆 𝑚 = 𝑇(2𝑚 ) obtain
𝑆 𝑚 = 2𝑆 𝑚Τ2 + 𝑚, already solved ! 𝑆 𝑚 = 𝑂(𝑚𝑙𝑔𝑚)
So, 𝑇 𝑛 = 𝑇 2𝑚 = 𝑆 𝑚 = 𝑂(𝑚𝑙𝑔𝑚)
Set 𝑚 back & obtain: 𝑶(𝒍𝒈𝒏(𝒍𝒈𝒍𝒈𝒏))
Recursion-tree method
◼ Each node represents the cost of a single subproblem
◼ Procedure:
❑ Sum the costs within each level of the tree to obtain a set of per-
level costs
❑ Sum all the per-level costs to determine the total cost of all levels
of recursion
◼ Use recursion tree to generate good guess then verify it by
the substitution method
◼ Careful and correct drawing of recursion-tree does not
require verification by substitution method
Recursion-tree method
◼ Example:
𝑇 𝑛 = 3𝑇 𝑛Τ4 + 𝜃(𝑛2 ).
Apply sloppiness where 𝑐 > 0 get
𝑇 𝑛 = 3𝑇 𝑛Τ4 + 𝑐𝑛2
Also, assume that 𝑛 is exact power of 4
Recursion-tree method
Recursion-tree method
◼ The subproblem size of each node at depth 𝑖 is 𝑛Τ4𝑖
◼ So, at the leaves, 𝑛Τ4𝑖 = 1 then 𝑖 = log 4 𝑛 is the index of
the last level and we have log 4 𝑛 + 1 number of levels
starting from 0
◼ Number of nodes at depth 𝑖 is 3𝑖
◼ Subproblem size at each level reduces by 4 then cost of a
𝑖 2
node at depth 𝑖 is 𝑐 𝑛Τ4 (except for the last level)
Recursion-tree method
𝑖 2 3 𝑖
◼ Then, total cost at depth 𝑖 is 3𝑖 𝑐 𝑛Τ4 = 𝑐𝑛2
16
where 𝑖 = 0, 1 … , log 4 𝑛 − 1
◼ Then, last level at depth log 4 𝑛 has 3log4 𝑛 nodes and each node
cost is 𝑇(1). Notice that 3log4 𝑛 = 𝑛log4 3
◼ So, the total cost for the bottom level is 𝜃(𝑛log4 3 )
◼ Total cost for the entire tree:
3 3 2 3 log4 𝑛−1
𝑇 𝑛 = 𝑐𝑛2 + 𝑐𝑛2 + 𝑐𝑛2 +⋯+ 𝑐𝑛2 + 𝜃(𝑛log4 3 )
16 16 16
log4 𝑛−1 3 𝑖
𝑇 𝑛 = σ𝑖=0 𝑐𝑛2 + 𝜃(𝑛log4 3 )
16
Recursion-tree method
3Τ16 log4 𝑛 − 1 2
𝑇 𝑛 = 𝑐𝑛 + 𝜃(𝑛log4 3 )
3Τ16 − 1
𝑥 𝑛+1 −1
◼ Above is true because σ𝑛𝑘=0 𝑥 𝑘 = when 𝑥 ≠1
𝑥−1
◼ But still complex ! So, make another sloppiness and let the
geometric series to go ∞
3 𝑖
◼ Then, 𝑇(𝑛) < σ∞
𝑖=0 16 𝑐𝑛2 + 𝜃(𝑛log4 3 ). So,
16 1
𝑇 𝑛 < 𝑐𝑛2 + 𝜃(𝑛 log4 3
) because, σ∞
𝑘=0 𝑥 𝑘
= when 𝑥 < 1
13 1−𝑥
◼ Therefore, the time complexity is 𝑶(𝒏𝟐 )
Recursion-tree method
◼ For verification by substitution method, use guess 𝑇 𝑛 = 𝑂(𝑛2 )
derived for the original recurrence 𝑇 𝑛 = 3𝑇 𝑛Τ4 + 𝜃(𝑛2 )
◼ We need to show that 𝑇(𝑛) ≤ 𝑑𝑛2 for some 𝑑 > 0
𝑇 𝑛 ≤ 3𝑇 𝑛Τ4 + 𝑐𝑛2
2
𝑇 𝑛 ≤ 3𝑑 𝑛Τ4 + 𝑐𝑛2
2
𝑇 𝑛 ≤ 3𝑑 𝑛Τ4 + 𝑐𝑛2
3
= 𝑑𝑛2 + 𝑐𝑛2 ≤ 𝑑𝑛2
16
2
𝑇(𝑛) ≤ 𝑑𝑛 holds when 𝑑 ≥ 16Τ13 𝑐
Recursion-tree method
Recursion-tree method
Master method
◼ Master theorem:
Let 𝑎 ≥ 1 and 𝑏 > 1 be constants, let Solve 𝑓 𝑛 be a
function, and let 𝑇(𝑛) be defined on the nonnegative
integers by the recurrence:
𝑇 𝑛 = 𝑎𝑇 𝑛Τ𝑏 + 𝑓(𝑛)
where we interpret 𝑛Τ𝑏 to mean either 𝑛Τ𝑏 or 𝑛Τ𝑏 .
Then, 𝑇(𝑛) can be bounded asymptotically as follows:
Master method
◼ Master theorem: (cntd.)
1. If 𝑓 𝑛 = 𝑂(𝑛log𝑏 𝑎−𝜖 ) for some constant 𝜖 > 0 then
𝑇 𝑛 = 𝜃(𝑛log𝑏 𝑎 )
2. If 𝑓 𝑛 = 𝜃(𝑛log𝑏 𝑎 ) then
𝑇 𝑛 = 𝜃(𝑛log𝑏 𝑎 𝑙𝑔𝑛)
3. If 𝑓 𝑛 = Ω(𝑛log𝑏 𝑎+𝜖 ) for some constant 𝜖 > 0 and
if 𝑎𝑓(𝑛Τ𝑏) ≤ 𝑐𝑓(𝑛) for some constant 𝑐 < 1 and all
sufficiently large 𝑛 then
𝑇 𝑛 = 𝜃(𝑓 𝑛 )
Master method
◼ We compare 𝑓(𝑛) with 𝑛log𝑏 𝑎
if 𝑓 𝑛 < 𝑛log𝑏 𝑎 then case 1 (polynomially smaller)
if 𝑓 𝑛 > 𝑛log𝑏 𝑎 and … then case 3
if 𝑓 𝑛 = 𝑛log𝑏 𝑎 then case 2 (polynomially larger)
◼ Example: Solve 𝑇 𝑛 = 9𝑇 𝑛Τ3 + 𝑛
𝑎 = 9, 𝑏 = 3, 𝑓(𝑛) = 𝑛 then 𝑛log𝑏 𝑎 = 𝑛log3 9 = 𝜃(𝑛2 )
Since 𝑓 𝑛 = 𝑛 = 𝑂(𝑛log3 9−𝜖 ) where 𝜖 = 1 Case 1 then
acc. to the Master Theorem: 𝑇 𝑛 = 𝜃 𝑛log3 9 = 𝜃(𝑛2 )
Master method
◼ Example: Solve 𝑇 𝑛 = 𝑇 2𝑛Τ3 + 1
𝑎 = 1, 𝑏 = 3/2, 𝑓(𝑛) = 1 then 𝑛log𝑏 𝑎 = 𝑛log3/2 1 = 𝑛0 = 1
Since 𝑓 𝑛 = 1 = 𝜃 𝑛log3/2 1 = 𝜃(1) Case 2 then
acc. to the Master Theorem:
𝑇 𝑛 = 𝜃 𝑛log3/2 1 𝑙𝑔𝑛 = 𝜃(𝑙𝑔𝑛)
Master method
◼ Example: Solve 𝑇 𝑛 = 3𝑇 𝑛/4 + 𝑛𝑙𝑔𝑛
𝑎 = 3, 𝑏 = 4, 𝑓(𝑛) = 𝑛𝑙𝑔𝑛 then 𝑛log𝑏 𝑎 = 𝑛log4 3 = 𝑂(𝑛0.793 )
Since 𝑓 𝑛 = 𝑛𝑙𝑔𝑛 = Ω 𝑛log4 3+𝜖 where 𝜖 ≈ 0.2 also
for sufficiently large 𝑛,
3
𝑎𝑓 𝑛Τ𝑏 = 3 𝑛Τ4 lg 𝑛Τ4 ≤ 𝑛𝑙𝑔𝑛 = 𝑐𝑓(𝑛) holds for 𝑐 = 3Τ4
4
which is < 1 as well, Case 3 then
acc. to the Master Theorem:
𝑇 𝑛 = 𝜃 𝑓(𝑛) = 𝜃 𝑛𝑙𝑔𝑛
Master method
◼ Example: Solve 𝑇 𝑛 = 2𝑇 𝑛/2 + 𝑛𝑙𝑔𝑛
𝑎 = 2, 𝑏 = 2, 𝑓(𝑛) = 𝑛𝑙𝑔𝑛 then 𝑛log𝑏 𝑎 = 𝑛log2 2 = 𝑛
𝑓 𝑛 = 𝑛𝑙𝑔𝑛 > 𝑛log2 2 = 𝑛
𝑓(𝑛) is asymptotically larger but not polynomially larger!
Neither Case 2 nor Case 3. Master Theorem can NOT be
applied!

You might also like