GATE CS 2021 Set 2 Q39 — Asymptotic Worst Case Time and Space Complexity

The given recurrence relation is:

where $a \geq 1$ and $b > 1$. This is the standard form analyzed by the Master Theorem. Let us evaluate each option based on the cases of the Master Theorem:

1. Analysis of Option C (Correct)

According to Case 1 of the Master Theorem:

If $f(n) = O(n^{\log_b(a) - \epsilon})$ for some constant $\epsilon > 0$, then the work done at the leaves dominates the recurrence. Thus, the time complexity is:

This matches Option C exactly.

2. Analysis of Other Options

• Option A: If $f(n) = n \log_2(n)$, the complexity $T(n)$ depends on the relationship between $f(n)$ and $n^{\log_b(a)}$. For example, if $a = 4$ and $b = 2$, then $n^{\log_b(a)} = n^2$. Since $f(n) = O(n^{2-\epsilon})$, Case 1 applies and $T(n) = \Theta(n^2)$, not $\Theta(n \log_2(n))$. Thus, Option A is incorrect in general.
• Option B: Since $T(n) = a T(n/b) + f(n)$ and $a \geq 1$, the overall complexity $T(n)$ must be at least $\Omega(f(n))$. If $f(n) = \frac{n}{\log_2(n)}$, then $T(n)$ cannot be $\Theta(\log_2(n))$ because $\frac{n}{\log_2(n)}$ grows strictly faster than $\log_2(n)$. Thus, Option B is incorrect.
• Option D: According to Case 2 of the Master Theorem, if $f(n) = \Theta(n^{\log_b(a)})$, then the work is evenly distributed across all levels of the recursion tree. The complexity is:
$$T(n) = \Theta(n^{\log_b(a)} \log n)$$

Therefore, Option D is incorrect.