Previously Asked GATE Questions on Recurrence Relations
Que – 1. What is the time complexity of Tower of Hanoi problem?
(A) T(n) = O(sqrt(n))
(D) T(n) = O(n^2)
(C) T(n) = O(2^n)
(D) None
Solution: For Tower of Hanoi, T(n) = 2T(n-1) + c for n>1 and T(1) = 1. Solving this,
T(n) = 2T(n-1) + c
= 2(2T(n-2)+ c) + c = 2^2*T(n-2) + (c + 2c)
= 2^k*T(n-k) + (c + 2c + .. kc)
Substituting k = (n-1), we get
T(n) = 2^(n-1)*T(1) + (c + 2c + (n-1)c) = O(2^n)
Que – 2. Consider the following recurrence:
T(n) = 2 * T(ceil (sqrt(n) ) ) + 1, T(1) = 1
Which one of the following is true?
(A) T(n) = (loglogn)
(B) T(n) = (logn)
(C) T(n) = (sqrt(n))
(D) T(n) = (n)
Solution: To solve this type of recurrence, substitute n = 2^m as:
T(2^m) = 2T(2^m /2) + 1
Let T(2^m) = S(m),
S(m) = 2S(m/2) + 1
Solving by master method, we get
S(m) = Θ(m)
As n = 2^m or m = log2n,
T(n) = T(2^m) = S(m) = Θ(m) = Θ(logn)
Que – 3. What is the value of following recurrence.
T(n) = T(n/4) + T(n/2) + cn2
T(1) = c
T(0) = 0
Where c is a positive constant
(A) O(n3)
(B) O(n2)
(C) O(n2 Logn)
(D) O(nLogn)
Answer: (B)
Que – 4. What is the value of following recurrence.
T(n) = 5T(n/5) + ,
T(1) = 1,
T(0) = 0
(A) Theta (n)
(B) Theta (n^2)
(C) Theta (sqrt(n))
(D) Theta (nLogn)
Answer: (A)
Que – 5. Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false. ( GATE CS 2005)
a) T(n) = O(n^2)
b) T(n) = θ(nLogn)
c) T(n) = Ω(n^2)
d) T(n) = O(nLogn)
(A) A
(B) B
(C) C
(D) D
Answer: (C)
Que – 6. The running time of an algorithm is represented by the following recurrence relation:
if n <= 3 then T(n) = n
else T(n) = T(n/3) + cn
Which one of the following represents the time complexity of the algorithm?
(A) θ(n)
(B) θ(n log n)
(C) θ(n^2)
(D) θ(n^2log n)
Answer: (A)
Que – 7. The running time of the following algorithm
Procedure A(n)
If n <= 2 return(1) else return A();
is best described by
(A) O(n)
(B) O(log n)
(C) O(1og log n)
(D) O(1)
Answer: (C)
Que – 8. The time complexity of the following C function is (assume n > 0 (GATE CS 2004)
int recursive (mt n)
{
if (n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}
(A) 0(n)
(B) 0(nlogn)
(C) 0(n^2)
(D) 0(2^n)
Answer: (D)
Que – 9. Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? (GATE-CS-2014-(Set-2))
T(n) = 2T(n/2) + Logn
(A) Θ(n)
(B) Θ(nLogn)
(C) Θ(n*n)
(D) Θ(log n)
Answer: (A)
Que – 10. Consider the recurrence relation a1 = 8, an = 6n2 + 2n + an-1. Let a99 = k x 104. The value of K is _____. (GATE-CS-2016 (Set 1))
Note : This question was asked as Numerical Answer Type.
(A) 190
(B) 296
(C) 198
(D) 200
Answer: (C)
Recurrence Relations Notes for GATE Exam [2024]Advanced master theorem for divide and conquer recurrences:
Recurrence relations are the mathematical backbone of algorithmic analysis, providing a systematic way to express the time complexity of recursive algorithms. As GATE Exam 2024 approaches, a profound understanding of recurrence relations becomes imperative for tackling questions that demand a deep comprehension of algorithmic efficiency. These notes aim to present a concise and illuminating guide to recurrence relations, covering key concepts and techniques that are likely to be assessed in the GATE examination.
Table of Content
- What is Recurrence Relations?
- What is Linear Recurrence Relation?
- How to Solve Recurrence Relations?
- 1. Substitution Method:
- 2. Recurrence Tree Method:
- 3. Master Method:
- Different types of recurrence relations and their solutions:
- Previously Asked GATE Questions on Recurrence Relations: