GATE 2025 CS1 Q.20: solution and answer

GATE 2025 · CS1Q.20 · 1 mark · MCQ

Consider the following recurrence relation:

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

Which ONE of the following options is CORRECT?

(A)
$T (n) = Θ (n^{2} 2^{n})$
(B)
$T (n) = Θ (n 2^{n})$
(C)
$T (n) = Θ ((lo g n)^{2} 2^{n})$
(D)
$T (n) = Θ (4^{n})$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

T(n) = Θ(n²2ⁿ) — option (A).

Official answer: ASource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

Recurrence: T(n) = 2T(n-1) + n·2ⁿ for n > 0, with base case T(0) = 1.
Define S(n) = T(n)/2ⁿ to normalize out the exponential growth, so T(n) = 2ⁿS(n) and T(n-1) = 2^{n-1}S(n-1).
Substituting into the recurrence: 2ⁿS(n) = 2·2^{n-1}S(n-1) + n·2ⁿ = 2ⁿS(n-1) + n·2ⁿ. Dividing both sides by 2ⁿ gives S(n) = S(n-1) + n, with S(0) = T(0)/2⁰ = 1.
Unrolling this simple additive recurrence: S(n) = S(0) + (1 + 2 + ... + n) = 1 + n(n+1)/2.
Since S(n) = 1 + n(n+1)/2 is a quadratic polynomial in n, S(n) = Θ(n²).
Therefore T(n) = 2ⁿ·S(n) = 2ⁿ·Θ(n²) = Θ(n²2ⁿ), which is option (A).

KEY IDEA

When a recurrence has the form T(n) = 2T(n-1) + f(n)·2^n, dividing through by 2^n turns the exponential recurrence into a simple additive one: define S(n) = T(n)/2^n, and the recurrence collapses to S(n) = S(n-1) + f(n), which can be solved by direct summation.

WATCH OUT FOR

Solving the recurrence directly by repeated substitution and losing track of the accumulating n·2^n terms (or mis-summing them) leads to an off-by-one-degree answer such as Θ(n2ⁿ) (option B) or assuming the extra n factor doesn't compound, missing that it must be summed over n terms to give the n² factor.

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

GATE 2025 CS1 Q.20: solution and answer

Answer and solution

More Complexity questions