The GATE Grind

GATE 2025 CS (CS1) – Question 20

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

Consider the following recurrence relation:
$T(n) = 2T(n-1) + n2^n$ for $n > 0$, $T(0) = 1$.

Which ONE of the following options is CORRECT?

  1. $T(n) = \Theta(n^2 2^n)$
  2. $T(n) = \Theta(n 2^n)$
  3. $T(n) = \Theta((\log n)^2\, 2^n)$
  4. $T(n) = \Theta(4^n)$

Practise this question in The GATE Grind →

Show answer and explanation

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

Explanation

Dividing by 2^n gives T(n)/2^n = T(n-1)/2^(n-1) + n. So T(n)/2^n = 1 + n(n+1)/2 and T(n) = Θ(n^2 2^n).