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) + cn²
T(1) = c
T(0) = 0

Where c is a positive constant

(A) O(n³)
(B) O(n²)
(C) O(n² 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 a₁ = 8, a_n = 6n² + 2n + a_n-1. Let a₉₉ = k x 10⁴. 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 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.