Recurrence
Recurrence
Introduction
} Many algorithms (divide and conquer) are recursive in nature.
} When we analyze them, we get a recurrence relation for time complexity.
} We get running time as a function of 𝒏 (input size) and we get the running time on inputs of
smaller sizes.
} A recurrence is a recursive description of a function, or a description of a function in terms of
itself.
} A recurrence relation recursively defines a sequence where the next term is a function of the
previous terms.
Methods to Solve Recurrence
} Substitution
} Recurrence tree
} Master method
Substitution Method – Example 1
} We make a guess for the solution and then we use mathematical induction to prove the guess
is correct or incorrect.
Time to solve the
Example 1: instance of size 𝑛 − 1
𝑻 𝒏 = 𝟎 + 𝟏 + 𝟐 + …+ 𝒏
𝒏 𝒏+𝟏
𝑻 𝒏 = = 𝑶 𝒏𝟐
𝟐
Substitution Method – Example 2
𝑐1 𝑖𝑓 𝑛 = 0
𝑡 𝑛 =6
𝑐2 + 𝑡 𝑛 − 1 𝑜/𝑤
1 if n = 0 or 1
1. T n = 6
T n − 1 + n − 1 o/w
𝒏⁄𝒃 𝒏⁄𝒃
Example 1: 𝑻(𝒏) = 𝟐𝑻(𝒏/𝟐) + 𝒏
Recurrence Tree Method
The recursion tree for this recurrence is § When we add the values across the levels of
the recursion tree, we get a value of 𝑛 for
every level.
𝑛
§ The bottom level has 2&'( ) nodes, each
contributing the cost 𝑇(1).
𝑛⁄2 𝑛⁄2 𝒏
𝒍𝒐𝒈𝟐 𝒏 § We have 𝑛 + 𝑛 + 𝑛 + …… log 𝑛
𝑡𝑖𝑚𝑒𝑠
𝒍𝒐𝒈𝟐 𝒏1𝟏
𝑛⁄23 𝑛⁄23 𝑛⁄23 𝑛⁄23 𝒏
𝑻(𝒏) = T 𝒏 + 𝟐𝒍𝒐𝒈 𝒏 𝑻(𝟏)
𝒊+𝟎
1 1 1 1 𝑻 𝒏 = 𝒏 𝒍𝒐𝒈 𝒏 + 𝒏
𝑻 𝒏 = 𝑶(𝒏 log 𝒏)
Example 2: 𝑻(𝒏) = 𝑻(𝒏/𝟑) + 𝑻(𝟐𝒏/𝟑) + 𝒏
Recurrence Tree Method
The recursion tree for this recurrence is § When we add the values across the levels of
the recursion tree, we get a value of 𝑛 for
every level.
&'("/$ )16
𝑛
𝑇(𝑛) = T 𝑛 + 𝑛&'("/$ 3𝑇(1)
4+5
𝑛⁄3 2𝑛⁄3 𝒏
𝒍𝒐𝒈𝟑 𝒏 𝒍𝒐𝒈𝟑/𝟐 𝒏 𝑻(𝒏) ∈ 𝒏 log 𝟑/𝟐 𝒏
1𝑛 2𝑛 1 2𝑛 2 2𝑛 𝒏
33 33 3 3 3 3
Example 3: 𝑻(𝒏) = 𝟐𝑻(𝒏/𝟐) + 𝒄. 𝒏𝟐
Recurrence Tree Method
The recursion tree for this recurrence is § Sub-problem size at level 𝑖 is )⁄3%
) 3
§ Cost of problem at level 𝑖 Is ⁄3%
§ Total cost,
𝒍𝒐𝒈𝟐 𝒏1𝟏 𝒊
𝟏
𝑛3 𝑻 𝒏 ≤ 𝒏𝟐 T
𝟐
𝒊+𝟎
7
𝑛⁄2 %
𝑛⁄2 3 1⁄2 𝑛3 𝟏 𝒊
𝟐
𝑻 𝒏 ≤𝒏 T
𝟐
𝒊+𝟎
𝑻 𝒏 = 𝑶 𝒏𝟐
𝑂 𝑛3
Recurrence Tree Method - Exercises
} Example 1: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(3𝑛/4) + 𝑐. 𝑛
} Example 2: 𝑇(𝑛) = 3𝑇(𝑛/4) + 𝑐. 𝑛2
} Example 3: 𝑇(𝑛) = 𝑇(𝑛/4) + 𝑇(𝑛/2) + 𝑛2
} Example 4: 𝑇(𝑛) = 𝑇(𝑛/3) + 𝑇(2𝑛/3) + 𝑛
Master Theorem
} The master theorem is a cookbook method for solving recurrences.
Time to divide &
} Suppose you have a recurrence of the form recombine
𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)
Given, a = 2, b = 2,
f(n) = 𝜃(1)
= 𝜃 𝑛4 (log 𝑛)4
𝑘 = 0, 𝑝 = 0
𝑙𝑜𝑔55 = 1 > 𝑘 = 0
/01##
Case1 :𝜃(𝑛 ) = 𝜃(𝑛3 )
Example 2: 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛
𝑙𝑜𝑔56 = 2 > 𝑘 = 1 , p = 0
therefore case 1: 𝜃(𝑛5 )
Solve Examples:
1. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛
2. 𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛5
Master Theorem for dividing function
Case 1:
Solve for:
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛𝑙𝑜𝑔𝑛
Master Theorem For Subtract and Conquer/Decreasing
Recurrences
Let T(n) be a function defined on positive n as shown below:
For some constants c, a>0, b>0, k>=0 and function f(n). If f(n) is O(nk), then
1. If a<1 then T(n) = O(nk)
2. If a=1 then T(n) = O(nk+1)
3. If a>1 then T(n) = O(nkan/b)
Examples :
Recurrence Relation Examples: Substitution Method
T(n) = T(n-1) + 1
void Test(int n)
{
if(n>0)
{
printf(“%d”,n);
Test(n-1);
}
}
Test(3)
3 Test(2)
2 Test(1)
1 Test(0)
T(n) = T(n-1) + 1
1 𝑛=0
T(n) =
T(n−1) + 1 𝑛 > 0
Substitute T(n-1)
T(n) = [T(n-2) + 1] + 1
T(n) = T(n-2) + 2
T(n) = [T(n-3) + 1] + 2
T(n) = T(n-3) + 3
…
Continue for k times
T(n) = T(n-k) + k
1 𝑛=0
T(n) =
T(n−1) + 1 𝑛 > 0
Substitute T(n-1)
T(n) = [T(n-2) + 1] + 1
T(n) = T(n-2) + 2
T(n) = [T(n-3) + 1] + 2
T(n) = T(n-3) + 3
…
Continue for k times
T(n) = T(n-k) + k
Assume n-k= 0
n=k
T(n) = T(n-n) + n
T(n) = T(0) + n
T(n) = 1 + n
O(n)
Recurrence Relation
T(n) = T(n-1) + n
Recurrence Relation
void Test(int n)
{
if(n > 0) 1
{
for(i=0; i < n ; i++) n+1
{
printf(“%d”, n); n
}
Test(n-1) T(n-1)
}
}
T(n) = T(n-1) + 2n+2
Recurrence Relation
1 𝑛=0
T(n) =
T(n−1) + 𝑛 𝑛 > 0
T(n)
n T(n-1)
n-1 T(n-2)
n-2 T(n-3)
…
1 T(0)
Recurrence Relation
1 𝑛=0
T(n) =
T(n−1) + 𝑛 𝑛 > 0
T(n) n
n T(n-1) n-1
n-2 T(n-3) …
…
1 T(0)
Recurrence Relation
1 𝑛=0
T(n) =
T(n−1) + 𝑛 𝑛 > 0
T(n) n
n T(n-1) n-1
1 T(0)
Recurrence Relation
T(n) = T(n-1) + n
T(n) = T(n-2) + (n-1)+n
T(n) = T(n-3) + (n-2)+(n-1)+n
Assume (n-k)=0
n=k
T(n) = T(0) + 1 + 2 + 3 + …..+(n-1)+n
= 1 + n(n+1)/2
𝑶(𝒏𝟐 )
Recurrence Relation
T(n)
𝑙𝑜𝑔𝑛 T(n-1)
𝑙𝑜𝑔(𝑛 − 1) T(n-2)
𝑙𝑜𝑔(𝑛 − 2) T(n-3)
…
1 T(0)
1 𝑛=0
T(n) =
T(n−1) + 𝑙𝑜𝑔𝑛 𝑛 > 0
T(n)
logn T(n-1)
log(n-1) T(n-2)
log1+log2+……….log(n-1)+logn =log(n x n-1 x …x 2 x 1)
=logn! log(n-2) T(n-3)
𝑂(𝑛𝑙𝑜𝑔𝑛)
…
1 T(0)
1 𝑛=0
T(n) =
T(n−1) + 𝑙𝑜𝑔𝑛 𝑛 > 0
Putting 𝑛 − 𝑘 = 0
T(n) = 2T(n-1) + 1
Algorithm Test (int n)
{
if(n > 0)
{
printf(“%d”,n);
Test(n-1);
Test(n-1);
}
}
Recurrence Relation
T(n)=2T(n-1)+1
Recurrence Relation
1 𝑛=0
T(n) =
2T(n−1) + 1 𝑛 > 0
T(n)
1 T(n-1) T(n-1)
%.(!!"# − 1)
a=1, r=2 =
!(%
Assume n-k=0
O(2* )
Recurrence Relation
1 𝑛=0
T(n) =
2T(n−1) + 1 𝑛 > 0
By substitution,
Assume 𝑛 − 𝑘 = 0
T(n) = 2*$% – 1
O(2* )
Recurrence Relation for Root Function
void Test(int n) T(n)
{
if(n > 2)
{
stmt; 1
Test( 𝑛); T( 𝑛)
}
}
Recurrence Relation: T(n) = T( 𝑛) + 1
1 𝑛=2
T(n) =
T( 𝑛)+ 1 𝑛>2
T(n )= T( 𝑛) + 1
#
T(n) = T(𝑛 ) + 1
$
#
T(n) = T(𝑛 ) + 2
$$
#
T(n) = T(𝑛 ) + 3
$%
⋮
#
T(n) = T(𝑛 ) + k
$!
Assume n = 2+
&
T(2+ ) = T(2 ) + k
$!
&
Assume T(2 ) = T(2% )
$!
+
Therefore, !! = 1
𝑚 = 2# and k = log ! 𝑚
Since 𝑛 = 2+ , m = log ! 𝑛
k = log log ! 𝑛
𝜽(log 𝐥𝐨𝐠 𝟐 𝒏)
Recursion Tree-
• Like Master’s Theorem, Recursion Tree is another method for solving the
recurrence relations.
• A recursion tree is a tree where each node represents the cost of a certain
recursive sub-problem.
• We sum up the values in each node to get the cost of the entire algorithm.
1. This is a modal window.
The media playback was aborted due to a corruption problem or because the media used
features your browser did not support.
Advertisement: 0:15
2.
Steps to Solve Recurrence Relations Using Recursion Tree
Method-
Step-01:
Step-02:
Determine-
• Cost of each level
• Total number of levels in the recursion tree
• Number of nodes in the last level
• Cost of the last level
Step-03:
Add cost of all the levels of the recursion tree and simplify the expression so obtained in
terms of asymptotic notation.
Solution-
Step-01:
This is illustrated through following recursion tree where each node represents the cost
of the corresponding sub-problem-
Step-02:
Step-03:
Step-04:
Step-05:
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained
in terms of asymptotic notation-
= n x log2n + θ (n)
= nlog2n + θ (n)
= θ (nlog2n)
Problem-02:
Solution-
Step-01:
This is illustrated through following recursion tree where each node represents the cost
of the corresponding sub-problem-
Step-02:
Step-03:
Determine total number of levels in the recursion tree. We will consider the rightmost sub
tree as it goes down to the deepest level-
Step-04:
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained
in terms of asymptotic notation-
= nlog5/4n + θ(nlog5/42)
= θ(nlog5/4n)
Problem-03:
Solution-
Step-01:
Step-02:
Step-03:
Step-04:
Step-05:
Step-06:
Add costs of all the levels of the recursion tree and simplify the expression so obtained
in terms of asymptotic notation-
2. if a = bk, then
(a) if p > -1, then T(n) = θ(nlog a logp+1n)
b
T(n) = θ(logn)
• Example-2: Merge Sort – T(n) = 2T(n/2) + O(n)
a = 2, b = 2, k = 1, p = 0
bk = 2. So, a = bk and p > -1 [Case 2.(a)]
T(n) = θ(nlog a logp+1n)
b
T(n) = θ(nlogn)
• Example-3: T(n) = 3T(n/2) + n2
a = 3, b = 2, k = 2, p = 0
bk = 4. So, a < bk and p = 0 [Case 3.(a)]
T(n) = θ(nk logpn)
T(n) = θ(n2)
T(n) = θ(nlog 3)
2
T(n) = θ(nlog3n)
for some constants c, a>0, b>0, k>=0 and function f(n). If f(n) is O(n k), then
1. If a<1 then T(n) = O(nk)
2. If a=1 then T(n) = O(nk+1)
3. if a>1 then T(n) = O(nkan/b)
• Example-1:
T(n) = 3T(n-1), n>0
= c, n<=0
Sol:a=3, b=1, f(n)=0 so k=0;
Since a>0, T(n) = O(nkan/b)
T(n)= O(n03n/1)
T(n)= 3n
• Example-2:
T(n) = T(n-1) + n(n-1), if n>=2
= 1, if n=1
Sol:a=1, b=1, f(n)=n(n-1) so k=2;
Since a=1, T(n) = O(nk+1)
T(n)= O(n2+1)
T(n)= O(n3)
• Example-3:
T(n) = 2T(n-1) – 1, if n>0
= 1, if n<=0
Sol: This recurrence can’t be solved using above method
since function is not of form T(n) = aT(n-b) + f(n)