GATE CS 2024 Set 2 Q.15: Asymptotic Analysis and Time/Space Complexity

Let $T(n)$ be the recurrence relation defined as follows:

$T(0) = 1$ ,
$T(1) = 2$ , and
$T(n) = 5T(n - 1) - 6T(n - 2)$ for $n \ge 2$

Which one of the following statements is TRUE?

$T(n) = \Theta(2^n)$

$T(n) = \Theta(n2^n)$

$T(n) = \Theta(3^n)$

$T(n) = \Theta(n3^n)$

Official answer and solution

Official answer: A
From: Official GATE 2024 answer key

Solution

Solve the linear homogeneous recurrence relation using its characteristic equation and substitute the initial conditions $T(0)=1, T(1)=2$ to find the coefficients.

The characteristic equation of $T(n) - 5T(n-1) + 6T(n-2) = 0$ is: $r^2 - 5r + 6 = 0 \implies (r - 2)(r - 3) = 0 \implies r = 2, 3$
The general solution is $T(n) = c_1 2^n + c_2 3^n$ .
Substituting the given base cases $T(0) = 1$ $T (0) = 1$ and $T(1) = 2$ $T (1) = 2$ :
- For $n = 0$ : $c_1 + c_2 = 1$
- For $n = 1$ : $2c_1 + 3c_2 = 2$
  Solving this system gives $c_2 = 0$ and $c_1 = 1$ .
Because $c_2 = 0$ , the $3^n$ term vanishes completely, leaving the exact closed form: $T(n) = 2^n = \Theta(2^n)$

Final answer

Option (A)

Common trap

Choosing $\Theta(3^n)$ from the larger characteristic root $r = 3$ without checking that the initial conditions $T(0)=1, T(1)=2$ make the coefficient of $3^n$ equal to zero.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2024 Computer Science and Information Technology - Set 2 (CS2)
Question: 15 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source