Recurrences
Question 1 
For parameters a and b, both of which are ω(1), T(n) = T(n^{1/a})+1, and T(b)=1.
Then T(n) is
θ(log_{a} log_{b} n)  
θ(log_{b} log_{a} n)
 
θ(log_{2} log_{2} n)
 
θ(log_{ab} n)

Question 1 Explanation:
T(n) = T(n^{1/a}+1, T(b) = 1
T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
Question 2 
The solution of the recurrence relation T(m) = T(3m/4) + 1 is :
θ(lg m)  
θ(m)  
θ(mlg m)  
θ(lglg m)

Question 2 Explanation:
Using Masters Method:
a = 1, b = 4/3, k = 0, p = 0
Here, a = b^{k}
So, T(m) = n^{log a/ log b} log^{p+1} n
T(m) = θ(log m)
a = 1, b = 4/3, k = 0, p = 0
Here, a = b^{k}
So, T(m) = n^{log a/ log b} log^{p+1} n
T(m) = θ(log m)
Question 3 
The recurrence relation capturing the optimal execution time of the towers of Hanoi problem with n discs is:
T(n)=2T(n2)+2  
T(n)=2T(n/2)+1  
T(n)=2T(n2)+n  
T(n)=2T(n1)+1 
Question 3 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2 ^{2 }T(n – 2) + 3
⋮
= 2 ^{k} T( n – k) + (2 ^{k} – 1)
n – k = 1
= 2 ^{n1} T(1) + (2^{ n1} – 1)
= 2^{ n1} + 2^{ n1} – 1
= 2 ^{n} – 1
≌ O(2 ^{n} )
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 2 ^{2 }T(n – 2) + 3
⋮
= 2 ^{k} T( n – k) + (2 ^{k} – 1)
n – k = 1
= 2 ^{n1} T(1) + (2^{ n1} – 1)
= 2^{ n1} + 2^{ n1} – 1
= 2 ^{n} – 1
≌ O(2 ^{n} )
Question 4 
Time complexity of an algorithm T(n), where n is the input size is given by
T(n)=T(n1)+1/n, if n>1
=1, otherwise
The order of this algorithm is
logn  
n  
n ^{2 }  
n^{ n} 
Question 4 Explanation:
T (n) = T (n − 1 ) + 1/n
Question 5 
The running time of an algorithm T(n),where 'n' is the input size, is given by
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
n^{2}  
n^{n}  
n^{3}  
N 
Question 5 Explanation:
Apply master theorem.
a=8,b=2,k=0,p=0;
So, according to masters theorem, a>b ^{k}
=O(n^log _{2}^{ 8} )
=O(n^{ 3} )
a=8,b=2,k=0,p=0;
So, according to masters theorem, a>b ^{k}
=O(n^log _{2}^{ 8} )
=O(n^{ 3} )
Question 6 
The running time of an algorithm T(n),where 'n' is the input size, is given by
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
T(n)=8T(n/2)+qn, if n>1
=p, if n=1
Where p,q are constants. The order of this algorithm is
n^{ 2}  
n^{ n}  
n ^{3}  
N 
Question 6 Explanation:
The above recurrence is in the form of masters theorem.
Case1: a>b^{k}
Here, a=8,b=2,k=1,p=0
O(n(log _{2} 8))=O(n(log _{2} 2 ^{3} ))=O(n ^{3} (log_{ 2} 2)) [ log_{ 2} 2=1]
=O(n ^{3} )
Case1: a>b^{k}
Here, a=8,b=2,k=1,p=0
O(n(log _{2} 8))=O(n(log _{2} 2 ^{3} ))=O(n ^{3} (log_{ 2} 2)) [ log_{ 2} 2=1]
=O(n ^{3} )
Question 7 
For the recurrence relation T(n) = 2 + T(n  1), where T(0)=2, T(n)=?
n^{2}
 
2n+2  
log(n)  
2^{n} 
Question 7 Explanation:
T(n) = T(n1)+ 1
T(0) = 1
T(n1) = T(n11)+1
T(n) = [T(n2)+1] +1 = T(n2)+ 2
T(n2) = T(n21)+1
T(n) = [T(n3)+1]+1
= T(n3)+3
= T(n) = T(nk)+ k
Note: Let k = n
Then T(n) = T(0) + n = 1 + n
∴ O(n)
T(0) = 1
T(n1) = T(n11)+1
T(n) = [T(n2)+1] +1 = T(n2)+ 2
T(n2) = T(n21)+1
T(n) = [T(n3)+1]+1
= T(n3)+3
= T(n) = T(nk)+ k
Note: Let k = n
Then T(n) = T(0) + n = 1 + n
∴ O(n)
Question 8 
The solution of recurrence relation : T(n)=2T(sqrt(n))+lg(n) is
O(lg (n) lg(n))  
O(lg (n))  
O(n lg (n))  
O(lg (n) lg(lg(n))) 
Question 8 Explanation:
T (n) = l og log (n) · l og (n)
T (n) = l og(n) · l og log (n)
Question 9 
The asymptotic upper bound solution of the recurrence T(n)= 2T(n/2)+(n/lg) is relation given by
O(n^{2})  
O(n lg n)  
O(n lg lg n)  
O(lg lg n) 
Question 9 Explanation:
→ The above recurrence is not in the form of Masters theorem. It doesn't apply since f(n)=n/logn is n polynomially smaller than n^{log(base 2) 2e} for any epsilon>0.
We can apply after converting into n/logn as n*log^{1}n
2T(n/2)+n/logn is by taking a=2,b=2 ,k=1 ,p=1
T(n) = Θ(n^{log(base 2)2} log log n)
= O(n lg lg n)
We can apply after converting into n/logn as n*log^{1}n
2T(n/2)+n/logn is by taking a=2,b=2 ,k=1 ,p=1
T(n) = Θ(n^{log(base 2)2} log log n)
= O(n lg lg n)
Question 10 
Give asymptotic upper and lower bound for T(n) given below. Assume T(n) is constant for n≤2.
T(n)= 4T(√n)+lg^2 n
T(n)= θ(lg*(lg^2 n)lg n)  
T(n)= θ(lg^2n lg n)  
T(n)= θ(lg^2 n (lg lg n))  
T(n)= θ(lg (lg n)lg n) 
Question 10 Explanation:
Cosider m=log^2 n
T(2^m)=4T(2^(m/2))+m
Then S(m)=4(2^m) produces the recurrence:
S(m)=4S(m/2)+m
T(n)=T(2^m)
= S(m)=O(mlogm)
T(n)=O(lg^2 n (lg lgn))
Note: lg is nothing but log. Both are correct.
T(2^m)=4T(2^(m/2))+m
Then S(m)=4(2^m) produces the recurrence:
S(m)=4S(m/2)+m
T(n)=T(2^m)
= S(m)=O(mlogm)
T(n)=O(lg^2 n (lg lgn))
Note: lg is nothing but log. Both are correct.
Question 11 
Which of the following recurrence relation can be solved using Master theorem?
T(n) = 64T(n/8)  n  
T(n) =T(n/2) + n/(log n)  
T(n) =2^{n}T(n/2) + n  
T(n) =2T(n/2) + 1 
Question 11 Explanation:
Masters theorem is in the form of aT(n/b)+n^k log^p n
FALSE: T(n) = 64T(n/8)  n : In masters theorem will not support negative sign recurrence relation (64T(n/8)  n ).
FALSE: T(n) =T(n/2) + n/(log n) it is violated “non polynomial difference”. But we can write it n(log n) into n^1 logn but it violates non polynomial difference.
FALSE: In masters theorem “a” value must be greater than 1. But here they given exponential (2^n).
TRUE: T(n) =2T(n/2) + 1
a=2, b=2 , k=0 and p=0
a>b^k
=O(n^ log_b ^a n)
= O(n)
FALSE: T(n) = 64T(n/8)  n : In masters theorem will not support negative sign recurrence relation (64T(n/8)  n ).
FALSE: T(n) =T(n/2) + n/(log n) it is violated “non polynomial difference”. But we can write it n(log n) into n^1 logn but it violates non polynomial difference.
FALSE: In masters theorem “a” value must be greater than 1. But here they given exponential (2^n).
TRUE: T(n) =2T(n/2) + 1
a=2, b=2 , k=0 and p=0
a>b^k
=O(n^ log_b ^a n)
= O(n)
Question 12 
Time complexity of an algorithm whose recurrence equation is T(n)=4T(n/2)+n^{2} and T(1)=1 is expressed as ______
O(n^{2})  
O(n^{2} log n)  
O(n^{3})  
O(n log n) 
Question 12 Explanation:
Question 13 
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
T(n) = 2T(n2) + 2  
T(n) = 2T(n1) + n  
T(n) = 2T(n/2) + 1  
T(n) = 2T(n1) + 1 
Question 13 Explanation:
Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
T(n) = 2T(n1) + 1
This recurrence relation will give O(2^{n}) time complexity.
1) Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
T(n) = 2T(n1) + 1
This recurrence relation will give O(2^{n}) time complexity.
Question 14 
Solve the following recurrence relation:
T(n) = 4T(n/2) + n^{2}
Θ(n^{3})  
Θ(n^{2} logn)  
Θ(n^{2} /2)  
Θ(n^{2})

Question 14 Explanation:
T(n) = 4T(n/2) + n^{2}
a = 4, b = 2, k = 2, p = 0
So, a = b^{k} and p > 1
According to master’s theorem,
= O(n^{logba} log^{p+1}n)
= O(n^{2}log n)
a = 4, b = 2, k = 2, p = 0
So, a = b^{k} and p > 1
According to master’s theorem,
= O(n^{logba} log^{p+1}n)
= O(n^{2}log n)
Question 15 
Solve the following recurrence relation
T(n) = 4T(n/2) + nO(n^{2})
 
O(n/2)  
O(n)
 
O(logn)

Question 15 Explanation:
T(n) = 4T(n/2) + n
a = 4, b = 2, k = 1
Now, a> b^{k}
So according to master’s theorem,
O(n^{logba}) = O(n^{2})
a = 4, b = 2, k = 1
Now, a> b^{k}
So according to master’s theorem,
O(n^{logba}) = O(n^{2})
Question 16 
he running time of an algorithm T(n) where (n) is the input size, is given by
The order of the algorithm is
T(n) = 7T(n/2)+qn, if n>1 = p if n=1Where p, q are constants.
The order of the algorithm is
n^{2}  
n^{n}  
n^{3}  
n 
Question 16 Explanation:
T(n) = 7T(n/2) + qn
a=7, b=2, k=1
a > b^{k}, so Case 1 applies here.
Hence the answer is,
a=7, b=2, k=1
a > b^{k}, so Case 1 applies here.
Hence the answer is,
Question 17 
What is the asymptotic value for the recurrence equation T(n) = 2T(n/2) + n?
O(n)  
O(n^{2})  
O(n^{2} log n)  
O(n log n) 
Question 17 Explanation:
T(n) = 2T(n/2) + n
a=2, b=2, k=1, p=0
Now, a=b^{k} and p>1
So from Master’s theorem,
a=2, b=2, k=1, p=0
Now, a=b^{k} and p>1
So from Master’s theorem,
There are 17 questions to complete.