Course-B-Tech.
Type- Core
Course Code- CSET206 Course Name- DAA
Year- 2024 Semester- EVEN
Date- 25/01/2024 Batch- 2022-2025
CO-Mapping
CO1 CO2 CO3
Q1 √
Q2 √
Q3 √
Q4 √
Q5 √
Objectives
1. Students will be able to learn Recurrence relation using backward substitution.
2. Students will be able to learn Recursion tree method.
Questions:
Problem 1: Find the complexity of the below recurrence:
{ 3T(n-1), if n>0,
T(n) = { 1, otherwise
Ans:- O(3n)
Problem 2: Find the complexity of the recurrence:
{ 2T(n-1) – 1, if n>0,
T(n) = { 1, otherwise
Ans:- O(1)
Problem 3 Solve the following recurrence relation using recursion tree
method-
T(n) = 2T(n/2) + n
Ans:- 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.
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.
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
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
Determine cost of last level-
Cost of last level = n x T(1) = θ(n)
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 4: Solve the following recurrence relation using recursion tree
method-
T(n) = T(n/5) + T(4n/5) + n
Ans) 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.
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
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
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
Determine cost of last level-
Cost of last level = 2log5/4n x T(1) = θ(2log5/4n) = θ(nlog5/42)
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 5: Find the complexity of the below program:
void function(int n)
{
int count = 0;
for (int i=n/2; i<=n; i++)
for (int j=1; j+n/2<=n; j = j++)
for (int k=1; k<=n; k = k * 2)
count++;
}
Ans:- Time Complexity: O(n2logn).