Recurrences

Question 1

For parameters a and b, both of which are ω(1), T(n) = T(n1/a)+1, and T(b)=1.

Then T(n) is

A
θ(loga logb n)
B
θ(logb loga n)
C
θ(log2 log2 n)
D
θ(logab n)
       Algorithms       Recurrences       GATE 2020
Question 1 Explanation: 
T(n) = T(n1/a+1, T(b) = 1
T(n) = [T(n1/a2)+1] + 1
= [T(n1/a3)+1] + 2
= [T(n1/a3)] + 3
= [T(n1/ak)] + b
= logb n = ak
= log logb n = k log a
= k= loga logb n
T(n)=1+loga logb n
T(n)=O(loga logb n)
Question 2

The solution of the recurrence relation T(m) = T(3m/4) + 1 is :

A
θ(lg m)
B
θ(m)
C
θ(mlg m)
D
θ(lglg m)
       Algorithms       Recurrences       UGC-NET CS 2018 JUNE Paper-2
Question 2 Explanation: 
Using Masters Method:
a = 1, b = 4/3, k = 0, p = 0
Here, a = bk
So, T(m) = nlog a/ log b logp+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:
A
T(n)=2T(n-2)+2
B
T(n)=2T(n/2)+1
C
T(n)=2T(n-2)+n
D
T(n)=2T(n-1)+1
       Algorithms       Recurrences       Nielit Scientist-B IT 4-12-2016
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​ n-1​ T(1) + (2​ n-1​ – 1)
= 2​ n-1​ + 2​ n-1​ – 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(n-1)+1/n, if n>1 =1, otherwise The order of this algorithm is
A
logn
B
n
C
n​ 2
D
n​ n
       Algorithms       Recurrences       Nielit Scientist-B CS 2016 march
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
A
n2
B
nn
C
n3
D
N
       Algorithms       Recurrences       Nielit Scientific Assistance IT 15-10-2017
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​ )
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
A
n​ 2
B
n​ n
C
n​ 3
D
N
       Algorithms       Recurrences       Nielit Scientific Assistance CS 15-10-2017
Question 6 Explanation: 
The above recurrence is in the form of masters theorem.
Case-1: a>bk
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)=?

A
n2
B
2n+2
C
log(n)
D
2n
       Algorithms       Recurrences       JT(IT) 2016 PART-B Computer Science
Question 7 Explanation: 
T(n) = T(n-1)+ 1
T(0) = 1
T(n-1) = T(n-1-1)+1
T(n) = [T(n-2)+1] +1 = T(n-2)+ 2
T(n-2) = T(n-2-1)+1
T(n) = [T(n-3)+1]+1
= T(n-3)+3
= T(n) = T(n-k)+ 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
A
O(lg (n) lg(n))
B
O(lg (n))
C
O(n lg (n))
D
O(lg (n) lg(lg(n)))
       Algorithms       Recurrences       UGC NET CS 2018-DEC Paper-2
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
A
O(n2)
B
O(n lg n)
C
O(n lg lg n)
D
O(lg lg n)
       Algorithms       Recurrences       UGC NET CS 2017 Jan- paper-3
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 nlog(base 2) 2-e for any epsilon>0.
We can apply after converting into n/logn as n*log-1n
2T(n/2)+n/logn is by taking a=2,b=2 ,k=1 ,p=-1
T(n) = Θ(nlog(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
A
T(n)= θ(lg*(lg^2 n)lg n)
B
T(n)= θ(lg^2n lg n)
C
T(n)= θ(lg^2 n (lg lg n))
D
T(n)= θ(lg (lg n)lg n)
       Algorithms       Recurrences       UGC-NET DEC-2019 Part-2
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.
Question 11
Which of the following recurrence relation can be solved using Master theorem?
A
T(n) = 64T(n/8) - n
B
T(n) =T(n/2) + n/(log n)
C
T(n) =2nT(n/2) + n
D
T(n) =2T(n/2) + 1
       Algorithms       Recurrences       CIL Part - B
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)
Question 12
Time complexity of an algorithm whose recurrence equation is T(n)=4T(n/2)+n2 and T(1)=1 is expressed as ______
A
O(n2)
B
O(n2 log n)
C
O(n3)
D
O(n log n)
       Algorithms       Recurrences       APPSC-2016-DL-CS
Question 12 Explanation: 
Question 13

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

A
T(n) = 2T(n-2) + 2
B
T(n) = 2T(n-1) + n
C
T(n) = 2T(n/2) + 1
D
T(n) = 2T(n-1) + 1
       Algorithms       Recurrences       APPSC-2016-DL-CA
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(n-1) + 1
This recurrence relation will give O(2n) time complexity.
Question 14

Solve the following recurrence relation:
T(n) = 4T(n/2) + n2

A
Θ(n3)
B
Θ(n2 logn)
C
Θ(n2 /2)
D
Θ(n2)
       Algorithms       Recurrences       CIL 2020
Question 14 Explanation: 
T(n) = 4T(n/2) + n2
a = 4, b = 2, k = 2, p = 0
So, a = bk and p > -1
According to master’s theorem,
= O(nlogba logp+1n)
= O(n2log n)
Question 15

Solve the following recurrence relation

T(n) = 4T(n/2) + n
A
O(n2)
B
O(n/2)
C
O(n)
D
O(logn)
       Algorithms       Recurrences       CIL 2020
Question 15 Explanation: 
T(n) = 4T(n/2) + n
a = 4, b = 2, k = 1
Now, a> bk
So according to master’s theorem,
O(nlogba) = O(n2)
Question 16
he running time of an algorithm T(n) where (n) is the input size, is given by
T(n) = 7T(n/2)+qn, if n>1
   = p if n=1 
Where p, q are constants.
The order of the algorithm is
A
n2
B
nn
C
n3
D
n
       Algorithms       Recurrences       TNPSC-2012-Polytechnic-CS
Question 16 Explanation: 
T(n) = 7T(n/2) + qn
a=7, b=2, k=1
a > bk, 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?
A
O(n)
B
O(n2)
C
O(n2 log n)
D
O(n log n)
       Algorithms       Recurrences       TNPSC-2017-Polytechnic-CS
Question 17 Explanation: 
T(n) = 2T(n/2) + n
a=2, b=2, k=1, p=0
Now, a=bk and p>-1
So from Master’s theorem,
There are 17 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com
error: Content is protected !!