GATE2025_CS1_Q20

Consider the following recurrence relation:

T(n) = 2T(n - 1) + n2ⁿ for n > 0, T(0) = 1.

Which ONE of the following options is CORRECT?

✅ Final Answer:

The correct answer is option (A) T(n) = Θ(n²2ⁿ).

🔹 Short Answer:

To solve the recurrence T(n) = 2T(n-1) + n·2ⁿ, we can divide the entire equation by 2ⁿ. This transforms it into T(n)/2ⁿ = T(n-1)/2ⁿ⁻¹ + n. By substituting S(n) = T(n)/2ⁿ, we get a simpler recurrence S(n) = S(n-1) + n. The solution to this is an arithmetic series, which is Θ(n²). Substituting back, we get T(n) = S(n) · 2ⁿ = Θ(n²) · 2ⁿ = Θ(n²·2ⁿ).

🔸 Long Answer:

Solving this recurrence relation can be done efficiently using a transformation method. The presence of the `2T(n-1)` term and the `2ⁿ` term suggests a substitution that simplifies the entire expression.

Step 1: Transform the Recurrence

We start with the given recurrence:

T(n) = 2T(n - 1) + n·2ⁿ

Let's divide the entire equation by 2ⁿ:

T(n) / 2ⁿ = (2T(n - 1)) / 2ⁿ + (n·2ⁿ) / 2ⁿ

Simplifying the first term on the right side (2 / 2ⁿ = 1 / 2ⁿ⁻¹):

T(n) / 2ⁿ = T(n - 1) / 2^n-1 + n

Step 2: Introduce a New Function

This new form is much simpler. Let's define a new function `S(n)` as:

S(n) = T(n) / 2ⁿ

Substituting `S(n)` into our transformed recurrence, we get:

S(n) = S(n - 1) + n

We also need the base case for `S(n)`. Given `T(0) = 1`:

S(0) = T(0) / 2⁰ = 1 / 1 = 1

Step 3: Solve the Simpler Recurrence

We now have a simple recurrence `S(n) = S(n-1) + n`. We can solve this by unrolling (or telescoping):

S(n) = S(n - 1) + n
= (S(n - 2) + n - 1) + n
= (S(n - 3) + n - 2) + n - 1 + n
...
= S(0) + 1 + 2 + ... + (n - 1) + n

We know `S(0) = 1` and the sum of the first `n` integers is `n(n+1)/2`. Substituting these values:

S(n) = 1 + [ n(n+1) / 2 ]
= 1 + (n² + n) / 2

Step 4: Find the Asymptotic Bound

The dominant term in the expression for `S(n)` is `n²/2`. Therefore, the asymptotic complexity of `S(n)` is:

S(n) = Θ(n²)

Step 5: Substitute Back to Find T(n)

Finally, we substitute the complexity of `S(n)` back into our definition `T(n) = S(n) · 2ⁿ`:

T(n) = Θ(n²) · 2ⁿ = Θ(n²2ⁿ)

This confirms that option (A) is the correct answer.

Bibliography:
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms. MIT Press. (Chapter 4: Divide-and-Conquer).
- Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Pearson. (Chapter 5: Divide and Conquer).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.