GATE 2024 CS2 Q.15: solution and answer

GATE 2024 · CS2Q.15 · 1 mark · MCQ

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

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

Which one of the following statements is TRUE?

(A)
$T (n) = Θ (2^{n})$
(B)
$T (n) = Θ (n 2^{n})$
(C)
$T (n) = Θ (3^{n})$
(D)
$T (n) = Θ (n 3^{n})$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

T(n) = Θ(2^n), i.e., option A.

Official answer: ASource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

The recurrence T(n) = 5T(n-1) - 6T(n-2) for n ≥ 2 is linear, homogeneous, with constant coefficients, so its closed form is determined by the characteristic equation.
Characteristic equation: $x^{2} - 5 x + 6 = 0$ , which factors as $(x - 2) (x - 3) = 0$ , giving roots $x = 2$ and $x = 3$ .
General solution: $T (n) = A \cdot 2^{n} + B \cdot 3^{n}$ for constants $A, B$ determined by the initial conditions.
Apply $T (0) = 1$ : $A + B = 1$ .
Apply $T (1) = 2$ : $2 A + 3 B = 2$ .
Subtract $2 (A + B) = 2$ from $2 A + 3 B = 2$ : $(2 A + 3 B) - (2 A + 2 B) = 2 - 2 \Rightarrow B = 0$ , so $A = 1$ .
Thus $T (n) = 2^{n}$ exactly. Verification: $T (2) = 5 (2) - 6 (1) = 4 = 2^{2}$ and $T (3) = 5 (4) - 6 (2) = 8 = 2^{3}$ , both consistent with the closed form.
Since $T (n) = 2^{n}$ exactly for all $n$ , $T (n) = Θ (2^{n})$ , which is option A.

KEY IDEA

A linear homogeneous recurrence with constant coefficients is solved via its characteristic equation; the roots give the exact closed form, and initial conditions pin down the coefficients.

WATCH OUT FOR

Assuming the larger root (3) always dominates the asymptotic growth without checking whether its coefficient in the closed form is actually zero — here the initial conditions force the coefficient of $3^{n}$ to vanish, so the recurrence in fact grows only as $2^{n}$ , not $3^{n}$ .

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 14 Complexity questions, with notes

GATE 2024 CS2 Q.15: solution and answer

Answer and solution

More Complexity questions