GATE CS 2025 Set 1 | Question 20

MCQ · 1 mark · −0.33

Consider the following recurrence relation:

\(T(n) = 2T(n - 1) + n2^{n}\) for \(n \gt 0\), \(T(0) = 1\).

Which ONE of the following options is CORRECT?

  1. Option A: \(T(n) = \Theta(n^{2}2^{n})\) (correct)
  2. Option B: \(T(n) = \Theta(n2^{n})\)
  3. Option C: \(T(n) = \Theta((\log n)^{2}2^{n})\)
  4. Option D: \(T(n) = \Theta(4^{n})\)

Answer

(A)

Explanation

Divide both sides by \(2^{n}\) and put \(S(n) = T(n)/2^{n}\). The recurrence becomes \(S(n) = S(n - 1) + n\) with \(S(0) = 1\).

So \(S(n) = 1 + (1 + 2 + \dots + n) = 1 + \frac{n(n+1)}{2}\), and \(T(n) = 2^{n}\left(1 + \frac{n(n+1)}{2}\right) = \Theta(n^{2}2^{n})\).

Answer: A