[go: up one dir, main page]

0% found this document useful (0 votes)
18 views65 pages

Recurrence

The document discusses recurrence relations, which are used to analyze the time complexity of recursive algorithms. It outlines methods to solve these recurrences, including substitution, recurrence trees, and the master theorem, providing examples for each method. The master theorem is particularly highlighted as a systematic approach for solving recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

ssbakshi2050
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)
18 views65 pages

Recurrence

The document discusses recurrence relations, which are used to analyze the time complexity of recursive algorithms. It outlines methods to solve these recurrences, including substitution, recurrence trees, and the master theorem, providing examples for each method. The master theorem is particularly highlighted as a systematic approach for solving recurrences of the form T(n) = aT(n/b) + f(n).

Uploaded by

ssbakshi2050
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/ 65

Recurrence Relation

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

Time to solve the 𝑻(𝒏) = 𝑻(𝒏 − 𝟏) + 𝒏 1


instance of size 𝑛
} Replacing 𝑛 by 𝑛 − 1 and 𝑛 − 2, we can write following equations.

𝑻 𝒏−𝟏 =𝑻 𝒏−𝟐 +𝒏−𝟏 2

𝑻 𝒏−𝟐 =𝑻 𝒏−𝟑 +𝒏−𝟐 3

} Substituting equation 3 in 2 and equation 2 in 1 we have now,


𝑻(𝒏) = 𝑻(𝒏 − 𝟑) + 𝒏 − 𝟐 + 𝒏 − 𝟏 + 𝒏 4
Substitution Method – Example 1
𝑻(𝒏) = 𝑻(𝒏 − 𝟑) + 𝒏 − 𝟐 + 𝒏 − 𝟏 + 𝒏 4

} From above, we can write the general form as,


𝑻 𝒏 = 𝑻 𝒏 − 𝒌 + (𝒏 − 𝒌 + 𝟏) + (𝒏 − 𝒌 + 𝟐) + … + 𝒏

} Suppose, if we take 𝑘 = 𝑛 then,


𝑻 𝒏 = 𝑻 𝒏 − 𝒏 + (𝒏 − 𝒏 + 𝟏) + (𝒏 − 𝒏 + 𝟐) + … + 𝒏

𝑻 𝒏 = 𝟎 + 𝟏 + 𝟐 + …+ 𝒏

𝒏 𝒏+𝟏
𝑻 𝒏 = = 𝑶 𝒏𝟐
𝟐
Substitution Method – Example 2
𝑐1 𝑖𝑓 𝑛 = 0
𝑡 𝑛 =6
𝑐2 + 𝑡 𝑛 − 1 𝑜/𝑤

} Rewrite the equation, 𝑡 𝑛 = 𝑐2 + 𝑡(𝑛 − 1)


} Now, replace 𝐧 by 𝐧 – 𝟏 and 𝐧 − 𝟐
𝑡 𝑛 − 1 = 𝑐2 + 𝑡(𝑛 − 2) ∴ 𝑡 𝑛 − 1 = 𝑐2 + 𝑐2 + 𝑡(𝑛 − 3)
𝑡 𝑛 − 2 = 𝑐2 + 𝑡(𝑛 − 3)
} Substitute the values of 𝐧 – 𝟏 and 𝐧 − 𝟐
𝑡 𝑛 = 𝑐2 + 𝑐2 + 𝑐2 + 𝑡(𝑛 − 3)
} In general,
𝑡 𝑛 = 𝑘𝑐2 + 𝑡(𝑛 − 𝑘)
} Suppose if we take 𝑘 = 𝑛 then,
𝑡 𝑛 = 𝑛𝑐2 + 𝑡 𝑛 − 𝑛 = 𝑛𝑐2 + 𝑡 0
𝑡(𝑛) = 𝑛𝑐2 + 𝑐1 = 𝑶 𝒏
Substitution Method Exercises
} Solve the following recurrences using substitution method.

1 if n = 0 or 1
1. T n = 6
T n − 1 + n − 1 o/w

2. T (n) = T (n − 1) + 1 and T (1) = θ (1).


Recurrence Tree Method
} In recurrence tree, each node represents the cost of a single sub-problem in the set of
recursive function invocations.
} We sum the costs within each level of the tree to obtain a set of per level costs.
} Then we sum the all the per level costs to determine the total cost of all levels of the recursion.
} Here while solving recurrences, we divide the problem into sub-problems of equal size.
} E.g., 𝑇(𝑛) = 𝑎 𝑇(𝑛/𝑏) + 𝑓(𝑛) where 𝑎 > 1 , 𝑏 > 1 and 𝑓(𝑛) is a given function.
} 𝐹(𝑛) is the cost of splitting or combining the sub problems.

𝒏⁄𝒃 𝒏⁄𝒃
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
𝟐
𝒊+𝟎

𝑛⁄4 3 𝑛⁄4 3 𝑛⁄4 3 𝑛⁄4 3 1⁄4 𝑛3 𝑻 𝒏 ≤ 𝟐𝒏𝟐

𝑻 𝒏 = 𝑶 𝒏𝟐
𝑂 𝑛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
𝑇(𝑛) = 𝑎𝑇(𝑛/𝑏) + 𝑓(𝑛)

Number of sub- Time required to


problems solve a sub-problem

} This recurrence would arise in the analysis of a recursive algorithm.


} When input size 𝒏 is large, the problem is divided up into 𝒂 sub-problems each of size 𝒏/𝒃.
Sub-problems are solved recursively and results are recombined.
} The work to split the problem into sub-problems and recombine the results is 𝒇(𝒏).
Masters Theorem for Dividing Functions

𝑻(𝒏) = 𝒂𝑻(𝒏/𝒃) + 𝒇(𝒏)


where 𝑎 >= 1 and 𝑏 > 1, 𝑓(𝑛) = 𝜃(𝑛+ 𝑙𝑜𝑔, 𝑛)
First find out the value of : 1. 𝑙𝑜𝑔-.
2. 𝑘
Based on the values of 𝑙𝑜𝑔-. and 𝑘, we define 3 cases:
"
Case 1: if 𝑙𝑜𝑔-. > 𝑘, then 𝜃(𝑛 /01!
)
Case 2: if 𝑙𝑜𝑔-. =𝑘,
if p > -1 then 𝜃 𝑛+ 𝑙𝑜𝑔,23 𝑛
if p = -1 then 𝜃 𝑛+ 𝑙𝑜𝑔𝑙𝑜𝑔𝑛
if p < -1 then 𝜃 𝑛+
Case 3: if 𝑙𝑜𝑔-. < 𝑘,
if p>=0, then 𝜃 𝑛+ 𝑙𝑜𝑔, 𝑛
if p<0, then O(𝑛+ )
Example 1 : 𝑻(𝒏) = 𝟐𝑻(𝒏/𝟐) + 𝟏

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:

𝑇(𝑛) = 2𝑇(𝑛/2) + 1 𝑂(𝑛)


𝑇(𝑛) = 4𝑇(𝑛/2) + 1 𝑂(𝑛3 )
𝑇(𝑛) = 4𝑇(𝑛/2) + 𝑛 𝑂(𝑛5 )
𝑇(𝑛) = 8𝑇(𝑛/2) + 𝑛5 𝑂(𝑛7 )
𝑇(𝑛) = 16𝑇(𝑛/2) + 𝑛5 𝑂(𝑛6 )
Case 3:

𝑇(𝑛) = 𝑇(𝑛/2) + 𝑛 𝑂(𝑛)


𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛5 𝑂(𝑛5 )
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛5 𝑙𝑜𝑔𝑛 𝑂(𝑛5 𝑙𝑜𝑔𝑛)
Case 2:

𝑇(𝑛) = 𝑇(𝑛/2) + 1 O(𝑙𝑜𝑔𝑛)


𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛 O(𝑛𝑙𝑜𝑔𝑛)

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)

f(n) = n+1 calls


Complexity O(n)
void Test(int n) T(n)
{
if(n>0)
{
printf(“%d”,n); 1
Test(n-1); T(n-1)
}
}

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-1 T(n-2) 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-1 T(n-2) n-2

0+1+2+……….+n = n(n+1)/2 n-2 T(n-3) …


= 𝑶(𝒏𝟐 )

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

T(n) = T(n-k) + (n-(k-1)) + (n-(k-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

𝑻(𝒏) = 𝑻(𝒏 − 𝟏) + 𝒍𝒐𝒈𝒏


void Test(int n)
{
if(n > 0) 1
{
for(i=0; i < n ; i*2) log𝑛 + 1
{
printf(“%d”, n); 𝑙𝑜𝑔𝑛
}
Test(n-1) 𝑇(𝑛 − 1)
}
}
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑙𝑜𝑔𝑛
1 𝑛=0
T(n) =
T(n−1) + 𝑙𝑜𝑔𝑛 𝑛 > 0

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

𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑙𝑜𝑔𝑛

𝑇(𝑛) = [𝑇(𝑛 − 2) + log(𝑛 − 1)] + 𝑙𝑜𝑔𝑛

𝑇(𝑛) = [𝑇(𝑛 − 2) + log(𝑛 − 1)] + 𝑙𝑜𝑔𝑛

𝑇(𝑛) = [𝑇(𝑛 − 3) + log(𝑛 − 2)] + log(𝑛 − 1) + 𝑙𝑜𝑔𝑛

𝑇(𝑛) = 𝑇(𝑛 − 3) + log(𝑛 − 2) + log(𝑛 − 1) + 𝑙𝑜𝑔𝑛

𝑇(𝑛) = 𝑇(𝑛 − 𝑘) + log1 + log2 + … . + log(𝑛 − 1) + 𝑙𝑜𝑔𝑛

Putting 𝑛 − 𝑘 = 0

𝑇(𝑛) = 𝑇(0) + 𝑙𝑜𝑔𝑛!


𝑇 𝑛 = 1 + 𝑙𝑜𝑔𝑛!
𝑂(𝑛𝑙𝑜𝑔𝑛)
𝑇(𝑛) = 𝑇(𝑛 − 1) + 1 𝑂(𝑛)
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛 𝑂(𝑛! )
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑙𝑜𝑔𝑛 𝑂(𝑛𝑙𝑜𝑔𝑛)
𝑇(𝑛) = 𝑇(𝑛 − 1) + 𝑛^2 𝑂(𝑛" )
𝑇(𝑛) = 𝑇(𝑛 − 2) + 1 𝑂(𝑛)
𝑇(𝑛) = 𝑇(𝑛 − 100) + 𝑛 𝑂(𝑛! )

For recurrence like


𝑻(𝒏) = 𝟐𝑻(𝒏 − 𝟏) + 𝟏
??
Recurrence Relation

T(n) = 2T(n-1) + 1
Algorithm Test (int n)
{
if(n > 0)
{
printf(“%d”,n);
Test(n-1);
Test(n-1);
}
}
Recurrence Relation

Algorithm Test (int n) T(n)


{
if(n > 0)
{
printf(“%d”,n); 1
Test(n-1); Test(n-1)
Test(n-1); Test(n-1)
}
}

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 T(n-2) T(n-2) 1 T(n-2) T(n-2)


Recurrence Relation
1 𝑛=0
T(n) =
2T(n−1) + 1 𝑛 > 0

1+2+2! +…………….+ 2# = 2#$% -1

! # a(& !"# −1)


a + ar + a 𝑟 +……………..+a 𝑟 =
&(%

%.(!!"# − 1)
a=1, r=2 =
!(%
Assume n-k=0
O(2* )
Recurrence Relation
1 𝑛=0
T(n) =
2T(n−1) + 1 𝑛 > 0

By substitution,

𝑇(𝑛) = 2# 𝑇(𝑛 − 𝑘) + 2#(% + 2#(! + ………+ 2! +2+1

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:

Draw a recursion tree based on the given recurrence relation.

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.

Following problems clearly illustrates how to apply these steps.

PRACTICE PROBLEMS BASED ON RECURSION TREE-


Problem-01:

Solve the following recurrence relation using recursion tree method-


T(n) = 2T(n/2) + n

Solution-

Step-01:

Draw a recursion tree based on the given recurrence relation.

The given recurrence relation shows-


• A problem of size n will get divided into 2 sub-problems of size n/2.
• Then, each sub-problem of size n/2 will get divided into 2 sub-problems of size
n/4 and so on.
• At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-


The given recurrence relation shows-
• The cost of dividing a problem of size n into its 2 sub-problems and then
combining its solution is n.
• The cost of dividing a problem of size n/2 into its 2 sub-problems and then
combining its solution is n/2 and so on.

This is illustrated through following recursion tree where each node represents the cost
of the corresponding sub-problem-

Step-02:

Determine cost of each level-


• Cost of level-0 = n
• Cost of level-1 = n/2 + n/2 = n
• Cost of level-2 = n/4 + n/4 + n/4 + n/4 = n and so on.

Step-03:

Determine total number of levels in the recursion tree-


• Size of sub-problem at level-0 = n/20
• Size of sub-problem at level-1 = n/21
• Size of sub-problem at level-2 = n/22

Continuing in similar manner, we have-


Size of sub-problem at level-i = n/2i
Suppose at level-x (last level), size of sub-problem becomes 1. Then-
n / 2x = 1
2x = n
Taking log on both sides, we get-
xlog2 = logn
x = log2n

∴ Total number of levels in the recursion tree = log2n + 1

Step-04:

Determine number of nodes in the last level-


• Level-0 has 20 nodes i.e. 1 node
• Level-1 has 21 nodes i.e. 2 nodes
• Level-2 has 22 nodes i.e. 4 nodes

Continuing in similar manner, we have-


Level-log2n has 2log2n nodes i.e. n nodes

Step-05:

Determine cost of last level-


Cost of last level = n x T(1) = θ(n)

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:

Solve the following recurrence relation using recursion tree method-


T(n) = T(n/5) + T(4n/5) + n

Solution-

Step-01:

Draw a recursion tree based on the given recurrence relation.

The given recurrence relation shows-


• A problem of size n will get divided into 2 sub-problems- one of size n/5 and
another of size 4n/5.
• Then, sub-problem of size n/5 will get divided into 2 sub-problems- one of size
n/52 and another of size 4n/52.
• On the other side, sub-problem of size 4n/5 will get divided into 2 sub-problems-
one of size 4n/52 and another of size 42n/52 and so on.
• At the bottom most layer, the size of sub-problems will reduce to 1.

This is illustrated through following recursion tree-


The given recurrence relation shows-
• The cost of dividing a problem of size n into its 2 sub-problems and then
combining its solution is n.
• The cost of dividing a problem of size n/5 into its 2 sub-problems and then
combining its solution is n/5.
• The cost of dividing a problem of size 4n/5 into its 2 sub-problems and then
combining its solution is 4n/5 and so on.

This is illustrated through following recursion tree where each node represents the cost
of the corresponding sub-problem-

Step-02:

Determine cost of each level-


• Cost of level-0 = n
• Cost of level-1 = n/5 + 4n/5 = n
• Cost of level-2 = n/52 + 4n/52 + 4n/52 + 42n/52 = n

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-

• Size of sub-problem at level-0 = (4/5)0n


• Size of sub-problem at level-1 =(4/5)1n
• Size of sub-problem at level-2 =(4/5)2n

Continuing in similar manner, we have-


Size of sub-problem at level-i = (4/5)in
Suppose at level-x (last level), size of sub-problem becomes 1. Then-
(4/5)xn = 1
(4/5)x = 1/n
Taking log on both sides, we get-
xlog(4/5) = log(1/n)
x = log5/4n

∴ Total number of levels in the recursion tree = log5/4n + 1

Step-04:

Determine number of nodes in the last level-


• Level-0 has 20 nodes i.e. 1 node
• Level-1 has 21 nodes i.e. 2 nodes
• Level-2 has 22 nodes i.e. 4 nodes

Continuing in similar manner, we have-


Level-log5/4n has 2log5/4n nodes
Step-05:

Determine cost of last level-


Cost of last level = 2log5/4n x T(1) = θ(2log5/4n) = θ(nlog5/42)

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:

Solve the following recurrence relation using recursion tree method-


T(n) = 3T(n/4) + cn2

Solution-

Step-01:

Draw a recursion tree based on the given recurrence relation-


(Here, we have directly drawn a recursion tree representing the cost of sub problems)

Step-02:

Determine cost of each level-


• Cost of level-0 = cn2
• Cost of level-1 = c(n/4)2 + c(n/4)2 + c(n/4)2 = (3/16)cn2
• Cost of level-2 = c(n/16)2 x 9 = (9/162)cn2

Step-03:

Determine total number of levels in the recursion tree-


• Size of sub-problem at level-0 = n/40
• Size of sub-problem at level-1 = n/41
• Size of sub-problem at level-2 = n/42

Continuing in similar manner, we have-


Size of sub-problem at level-i = n/4i
Suppose at level-x (last level), size of sub-problem becomes 1. Then-
n/4x = 1
4x = n
Taking log on both sides, we get-
xlog4 = logn
x = log4n
∴ Total number of levels in the recursion tree = log4n + 1

Step-04:

Determine number of nodes in the last level-


• Level-0 has 30 nodes i.e. 1 node
• Level-1 has 31 nodes i.e. 3 nodes
• Level-2 has 32 nodes i.e. 9 nodes

Continuing in similar manner, we have-


Level-log4n has 3log4n nodes i.e. nlog43 nodes

Step-05:

Determine cost of last level-


Cost of last level = nlog43 x T(1) = θ(nlog43)

Step-06:

Add costs of all the levels of the recursion tree and simplify the expression so obtained
in terms of asymptotic notation-

= cn2 { 1 + (3/16) + (3/16)2 + ……… } + θ(nlog43)

Now, { 1 + (3/16) + (3/16)2 + ……… } forms an finite Geometric progression.


On solving, we get-
= (16/13)cn2 { 1 – (3/16)log4n } + θ(nlog43)
= (16/13)cn2 – (16/13)cn2 (3/16)log4n + θ(nlog43)
= O(n2)
Master Theorem
The Master Theorem is a tool used to solve recurrence relations that arise in
the analysis of divide-and-conquer algorithms. The Master Theorem provides
a systematic way of solving recurrence relations of the form:
T(n) = aT(n/b) + f(n)
1. where a, b, and f(n) are positive functions and n is the size of the
problem. The Master Theorem provides conditions for the solution
of the recurrence to be in the form of O(n^k) for some constant k,
and it gives a formula for determining the value of k.
2. The advanced version of the Master Theorem provides a more
general form of the theorem that can handle recurrence relations
that are more complex than the basic form. The advanced version of
the Master Theorem can handle recurrences with multiple terms
and more complex functions.
3. It is important to note that the Master Theorem is not applicable to
all recurrence relations, and it may not always provide an exact
solution to a given recurrence. However, it is a useful tool for
analyzing the time complexity of divide-and-conquer algorithms
and provides a good starting point for solving more complex
recurrences.
Master Theorem is used to determine running time of algorithms (divide and
conquer algorithms) in terms of asymptotic notations.
Consider a problem that is solved using recursion. So, according to master
theorem the runtime of the above algorithm can be expressed as:

T(n) = aT(n/b) + f(n)


where n = size of the problem
a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
f(n) = cost of work done outside the recursive calls like dividing into
subproblems and cost of combining them to get the solution.
Not all recurrence relations can be solved with the use of the master
theorem i.e. if

• T(n) is not monotone, ex: T(n) = sin n


• f(n) is not a polynomial, ex: T(n) = 2T(n/2) + 2 n
This theorem is an advance version of master theorem that can be used to
determine running time of divide and conquer algorithms if the recurrence is
of the following form :-

where n = size of the problem


a = number of subproblems in the recursion and a >= 1
n/b = size of each subproblem
b > 1, k >= 0 and p is a real number.
Then,

1. if a > bk, then T(n) = θ(nlog a)


b

2. if a = bk, then
(a) if p > -1, then T(n) = θ(nlog a logp+1n)
b

(b) if p = -1, then T(n) = θ(nlog a loglogn)


b

(c) if p < -1, then T(n) = θ(nlog a)


b

3. if a < bk, then


(a) if p >= 0, then T(n) = θ(nk logpn)
(b) if p < 0, then T(n) = θ(nk)

Time Complexity Analysis –

• Example-1: Binary Search – T(n) = T(n/2) + O(1)


a = 1, b = 2, k = 0 and p = 0
bk = 1. So, a = bk and p > -1 [Case 2.(a)]
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)

• Example-4: T(n) = 3T(n/2) + log2n


a = 3, b = 2, k = 0, p = 2
bk = 1. So, a > bk [Case 1]
T(n) = θ(nlog a )
b

T(n) = θ(nlog 3)
2

• Example-5: T(n) = 2T(n/2) + nlog2n


a = 2, b = 2, k = 1, p = 2
bk = 2. So, a = bk [Case 2.(a)]
T(n) = θ(nlog alogp+1n )
b

T(n) = θ(nlog 2log3n)


2

T(n) = θ(nlog3n)

• Example-6: T(n) = 2nT(n/2) + nn


This recurrence can’t be solved using above method since function
is not of form T(n) = aT(n/b) + θ(nk logpn)

• Master Theorem For Subtract and


Conquer Recurrences

Master theorem is used to determine the Big – O upper bound on functions


which possess recurrence, i.e which can be broken into sub problems.
Master Theorem For Subtract and Conquer 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(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)

You might also like