GATE CS 2025 Set 1 Q.20: Asymptotic Analysis and Time/Space Complexity

Consider the following recurrence relation:

T(n) = 2T(n - 1) + n 2^n \text{ for } n > 0, \quad T(0) = 1.

Which ONE of the following options is CORRECT?

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

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

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

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

Official answer and solution

Solution

Divide both sides of the recurrence by $2^n$ and telescope the resulting sum.

Dividing the recurrence $T(n) = 2T(n-1) + n 2^n$ by $2^n$ yields:

\frac{T(n)}{2^n} = \frac{T(n-1)}{2^{n-1}} + n

Let $S(n) = \frac{T(n)}{2^n}$ with $S(0) = \frac{T(0)}{2^0} = 1$ . Unrolling the recurrence gives:

S(n) = S(0) + \sum_{k=1}^{n} k = 1 + \frac{n(n+1)}{2} = \Theta(n^2)

Multiplying back by $2^n$ , we obtain:

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

Final answer

Option (A)

Common trap

Forgetting that $n$ terms of order $\Theta(k 2^n)$ sum to $\Theta(n^2 2^n)$ rather than $\Theta(n 2^n)$ .

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

Paper: GATE 2025 Computer Science and Information Technology - Session 1 (CS1)
Question: 20 of 65
Section: Computer Science and Information Technology

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