Question

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?

• 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) \)

Hint:

When solving recurrences with the recursion-tree method, focus on the number of levels and the work done at each level. The dominant term in the sum usually gives the asymptotic complexity.

Answer 1

The Correct Option is A

The recurrence relation given is:

\[ T(n) = 2T(n - 1) + n2^n. \]

We will solve this recurrence using the recursion-tree method and substitution method.

Step 1: Unfolding the recurrence:

Let's start by expanding the recurrence:
\[ T(n) = 2T(n - 1) + n2^n. \] Substituting for \( T(n - 1) \):
\[ T(n) = 2[2T(n - 2) + (n - 1)2^{n-1}] + n2^n = 2^2T(n - 2) + 2(n - 1)2^{n-1} + n2^n. \] Next, expand for \( T(n - 2) \):
\[ T(n) = 2^2[2T(n - 3) + (n - 2)2^{n-2}] + 2(n - 1)2^{n-1} + n2^n. \] This process continues. After \( k \) steps, we get:
\[ T(n) = 2^k T(n - k) + \sum_{i=0}^{k-1} 2^i (n - i) 2^{n-i}. \]

Step 2: Solving the recurrence:

As \( k \to n \), the last term where \( T(0) = 1 \) gives a small constant. The dominant term is the sum:
\[ \sum_{i=0}^{n-1} 2^i (n - i) 2^{n-i}. \] This simplifies to:
\[ T(n) = \Theta(n^2 2^n). \]
Thus, the correct answer is \( \boxed{A} \).