Consider the following recurrence relation: \(T(n) = 2T(n - 1) + n 2^n, \quad…
2025
Consider the following recurrence relation:
\(T(n) = 2T(n - 1) + n 2^n, \quad \text{for } n > 0, \quad T(0) = 1. \)
Which ONE of the following options is CORRECT?
- A.
\(T(n) = \Theta(n^2 2^n) \) - B.
\(T(n) = \Theta(n 2^n) \) - C.
\(T(n) = \Theta((\log n)^2 2^n) \) - D.
\(T(n) = \Theta(4^n)\)
Attempted by 93 students.
Show answer & explanation
Correct answer: A
Key idea: simplify the recurrence by dividing by 2^n.
Let S(n) = T(n)/2^n. Then
S(n) = T(n)/2^n = (2T(n-1))/2^n + n^2 = T(n-1)/2^{n-1} + n^2 = S(n-1) + n^2.
Unrolling gives S(n) = S(0) + sum_{i=1}^n i^2 = 1 + sum_{i=1}^n i^2.
Use the formula sum_{i=1}^n i^2 = n(n+1)(2n+1)/6 = Theta(n^3). So S(n) = 1 + Theta(n^3) = Theta(n^3).
Therefore T(n) = 2^n * S(n) = 2^n * Theta(n^3) = Theta(n^3 2^n).
Conclusion: The recurrence solves to Theta(n^3 2^n). The provided option that states Theta(n^2 2^n) underestimates the polynomial factor; the Theta(n 2^n) and Theta((log n)^2 2^n) options are also too small. Theta(4^n) is far too large since the recurrence produces 2^n times a polynomial factor, not an exponential 4^n growth.
A video solution is available for this question — log in and enroll to watch it.