GATE CS 2026 Set 2 Q15 — Asymptotic Worst Case Time and Space Complexity

To find which recurrence relations correspond to a time complexity of $\Theta(n)$, we analyze each option individually:

1. $T(n) = T(n-1) + 1, \quad T(1) = 1$
   Unrolling the recurrence: $$T(n) = T(n-1) + 1 = T(n-2) + 1 + 1 = \dots = T(1) + (n-1) \cdot 1$$ Substituting $T(1) = 1$: $$T(n) = 1 + n - 1 = n = \Theta(n)$$ Thus, Option A is correct.
2. $T(n) = 2 T\left(\frac{n}{2}\right) + 1, \quad T(1) = 1$
   Using the Master Theorem of the form $T(n) = a T(n/b) + f(n)$:
   • Here, $a = 2$, $b = 2$, and $f(n) = 1$.
   • We compare $f(n) = 1$ with $n^{\log_b a} = n^{\log_2 2} = n^1 = n$.
   • Since $f(n) = O(n^{1-\epsilon})$ for $\epsilon = 1$, we fall into Case 1 of the Master Theorem.
   Therefore: $$T(n) = \Theta(n^{\log_b a}) = \Theta(n)$$ Thus, Option B is correct.
3. $T(n) = 2 T\left(\frac{n}{2}\right) + n, \quad T(1) = 1$
   Using the Master Theorem:
   • Here, $a = 2$, $b = 2$, and $f(n) = n$.
   • We compare $f(n) = n$ with $n^{\log_b a} = n$.
   • Since $f(n) = \Theta(n^{\log_b a})$, we fall into Case 2 of the Master Theorem.
   Therefore: $$T(n) = \Theta(n \log n)$$ Thus, Option C is incorrect.
4. $T(n) = T(n-1) + n, \quad T(1) = 1$
   Unrolling the recurrence: $$T(n) = T(n-1) + n = T(n-2) + (n-1) + n = \dots = T(1) + 2 + 3 + \dots + n$$ Summing the arithmetic progression: $$T(n) = \frac{n(n+1)}{2} = \Theta(n^2)$$ Thus, Option D is incorrect.