Project ForgeAlgorithms
Complexity Analysis
GATE 2025
Hard
Consider the following recurrence relation: T(n) = 2T(n−1) + n·2^n for n > 0, T(0) = 1. Which ONE of the following options is CORRECT?
- T(n) = Θ(n²·2ⁿ)
- BT(n) = Θ(n·2ⁿ)
- CT(n) = Θ((log n)²·2ⁿ)
- DT(n) = Θ(4ⁿ)
Explanation
Divide both sides by 2^n: S(n) = T(n)/2^n satisfies S(n) = S(n−1) + n, with S(0)=1. This telescopes to S(n) = 1 + Σ(k=1 to n) k = 1 + n(n+1)/2 = Θ(n²). So T(n) = S(n)·2^n = Θ(n²·2ⁿ).
Source: GATE CS 2025 (Session 1 / CS1) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.