GATE CS 2009 Q35 — Asymptotic Worst Case Time and Space Complexity

We can solve the recurrence relation $T(n) = T\left(\frac{n}{3}\right) + cn$ using the Master Theorem or by expansion.

Method 1: Master Theorem
The recurrence is of the form $T(n) = a T\left(\frac{n}{b}\right) + f(n)$, where $a = 1$, $b = 3$, and $f(n) = cn = \Theta(n)$.

Comparing $f(n)$ with $n^{\log_b a} = n^{\log_3 1} = n^0 = 1$, we see that $f(n) = \Omega(n^{0 + \epsilon})$ for $\epsilon = 1$. The regularity condition $a f(n/b) \le k f(n)$ holds because $1 \cdot c\frac{n}{3} \le k \cdot cn$ for $k = \frac{1}{3} < 1$. By Case 3 of the Master Theorem, $T(n) = \Theta(f(n)) = \Theta(n)$.

Method 2: Expansion Method
Expanding the recurrence step-by-step:
$T(n) = T\left(\frac{n}{3}\right) + cn = T\left(\frac{n}{9}\right) + c\frac{n}{3} + cn = \dots = T\left(\frac{n}{3^k}\right) + cn \sum_{i=0}^{k-1} \left(\frac{1}{3}\right)^i$

The summation is a decreasing geometric series that converges to a constant factor $\frac{3}{2}$. Thus, $T(n) = \Theta(1) + \frac{3}{2}cn = \Theta(n)$.