Skip to content
GATETECH
Official PYQ · 2004Q84Asymptotic Worst Case Time and Space ComplexityMCQ1 mark

GATE CS 2004 Q84 — Asymptotic Worst Case Time and Space Complexity

Explain with AI

The recurrence equation
T(1)=1T(1) = 1
T(n)=2T(n−1)+n,n≥2T(n) = 2T(n-1) + n, n \geq 2

evaluates to

Choose one option
View worked solution

Answer: A

We can solve this recurrence relation using two approaches: a quick verification method for the exam, and a formal analytical derivation.

Method 1: Quick Verification

Let us compute the first few terms of the sequence using the recurrence relation:

  • T(1)=1T(1) = 1
  • T(2)=2T(1)+2=2(1)+2=4T(2) = 2T(1) + 2 = 2(1) + 2 = 4

Now, substitute n=2n = 2 into the given options:

  • Option A: 22+1−2−2=8−4=42^{2+1} - 2 - 2 = 8 - 4 = 4 (Matches)
  • Option B: 22−2=22^2 - 2 = 2 (Incorrect)
  • Option C: 22+1−2(2)−2=8−4−2=22^{2+1} - 2(2) - 2 = 8 - 4 - 2 = 2 (Incorrect)
  • Option D: 22+2=62^2 + 2 = 6 (Incorrect)

Method 2: Analytical Derivation

Expanding the recurrence relation by substitution:

T(n)=2T(n−1)+n=2[2T(n−2)+(n−1)]+n=22T(n−2)+2(n−1)+n=22[2T(n−3)+(n−2)]+2(n−1)+n=23T(n−3)+22(n−2)+2(n−1)+n  ⋮=2n−1T(1)+∑i=0n−22i(n−i)\begin{aligned} T(n) &= 2T(n-1) + n \\ &= 2[2T(n-2) + (n-1)] + n = 2^2 T(n-2) + 2(n-1) + n \\ &= 2^2[2T(n-3) + (n-2)] + 2(n-1) + n = 2^3 T(n-3) + 2^2(n-2) + 2(n-1) + n \\ &\ \ \vdots \\ &= 2^{n-1} T(1) + \sum_{i=0}^{n-2} 2^i (n-i) \end{aligned}

Since T(1)=1T(1) = 1, we have:

T(n)=2n−1+n∑i=0n−22i−∑i=0n−2i2iT(n) = 2^{n-1} + n \sum_{i=0}^{n-2} 2^i - \sum_{i=0}^{n-2} i 2^i

Using standard summation formulas for geometric and arithmetico-geometric series:

  • ∑i=0n−22i=2n−1−1\sum_{i=0}^{n-2} 2^i = 2^{n-1} - 1
  • ∑i=0n−2i2i=(n−3)2n−1+2\sum_{i=0}^{n-2} i 2^i = (n-3)2^{n-1} + 2

Substituting these back into the equation:

T(n)=2n−1+n(2n−1−1)−[(n−3)2n−1+2]=2n−1+n2n−1−n−n2n−1+3⋅2n−1−2=4⋅2n−1−n−2=2n+1−n−2\begin{aligned} T(n) &= 2^{n-1} + n(2^{n-1} - 1) - \left[(n-3)2^{n-1} + 2\right] \\ &= 2^{n-1} + n 2^{n-1} - n - n 2^{n-1} + 3 \cdot 2^{n-1} - 2 \\ &= 4 \cdot 2^{n-1} - n - 2 \\ &= 2^{n+1} - n - 2 \end{aligned}

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Asymptotic Worst Case Time and Space Complexity questions