GATE CS 1996 Q2.12 — Asymptotic Worst Case Time and Space Complexity

We can solve the recurrence relation $T(n) = 3T\left(\frac{n}{4}\right) + n$ using the Master Theorem for divide-and-conquer recurrences of the form $T(n) = aT\left(\frac{n}{b}\right) + f(n)$:

• Here, $a = 3$, $b = 4$, and $f(n) = n = \Theta(n^1)$.
• We compare $f(n)$ with $n^{\log_b a} = n^{\log_4 3}$.

Since $\log_4 3 \approx 0.792 < 1$, we have $f(n) = \Omega\left(n^{\log_4 3 + \epsilon}\right)$ for $\epsilon \approx 0.2$. This corresponds to Case 3 of the Master Theorem.

To confirm, we check the regularity condition: $a f\left(\frac{n}{b}\right) \le c f(n)$ for some constant $c < 1$.
$$3 \left(\frac{n}{4}\right) = \frac{3}{4}n \le c n \quad \text{for } c = \frac{3}{4} < 1$$

Since the regularity condition holds, the solution is $T(n) = \Theta(f(n)) = \Theta(n)$, which implies $T(n) = O(n)$.