The GATE Grind

GATE 2024 CS (CS2) – Question 15

Algorithms · Asymptotic Analysis and Time/Space Complexity · 1 mark · Multiple choice

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?

  1. $T(n)=\Theta(2^n)$
  2. $T(n)=\Theta(n2^n)$
  3. $T(n)=\Theta(3^n)$
  4. $T(n)=\Theta(n3^n)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (A) $T(n)=\Theta(2^n)$

Explanation

Characteristic roots are 2 and 3. T(n)=A·2^n+B·3^n; T(0)=1, T(1)=2 gives A+B=1 and 2A+3B=2, so B=0 and A=1. Hence T(n)=2^n.