Cases of Master Theorem

Question

Suppose that we have $ \\ T(n)=\left\{\begin{matrix} c, & \ \text{if } n<d\\ aT\left( \frac{n}{b} \right )+f(n), & \ \ \text{if } n \geq d \end{matrix}\right.$

The Master theorem is the following:

1. If $f(n)=O(n^{\log_b a- \epsilon})$, then $T(n)= \Theta(n^{\log_ba})$

2. If $f(n)= \Theta(n^{\log_b a} \log^k n)$, then $T(n)=\Theta(n^{\log_ba}\log^{k+1}n)$

3. If $f(n)=\Omega(n^{\log_b a+ \epsilon})$, then $T(n)= \Theta(f(n))$, provides $af\left(\frac{n}{b} \right) \leq \delta f(n)$ for some $\delta<1$ for all $n \geq d$.

Proof:

Using iterative substitution, let us see if we can find a pattern:

$$T(n)=aT\left( \frac{n}{b}\right)+f(n)=a \left(aT \left(\frac{n}{b^2} \right) +f\left( \frac{n}{b}\right)\right)+f(n)= \dots\\= a^{\log_bn}T(1)+ \sum_{i=0}^{(\log_bn)-1} a^i f\left( \frac{n}{b^i} \right)=n^{\log_b a} T(1)+ \sum_{i=0}^{(\log_b n)-1} a^i f\left(\frac{n}{b^i} \right)$$

We then distinguish the three cases as

• The first term is dominant
• Each part of the summation is equally dominant
• The summation is a geometric series

Don't we have to explain further which case correponds to which of the following cases

• The first term is dominant.
• Each part of the summation is equally dominant.
• The summation is a geometric series

and justify why it is like that? How could we justify it?

Answer 1

The three cases correspond exactly to the three cases in the statement of the theorem. Let's consider them one by one. Suppose for simplicity that $T(1) = 1$.

Case 1. Suppose that $f(n) = n^\delta$, where $\delta < \log_b a$. Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta < \log_b a$, we have $b^\delta < a$ and so $a/b^\delta > 1$. Therefore $$ \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i = \left(\frac{a}{b^\delta}\right)^{\log_b n} \sum_{j=1}^{\log_b n} \left(\frac{b^\delta}{a}\right)^j = \Theta(n^{\log_b a - \delta}), $$ since the geometric series $\sum_j (b^\delta/a)^j$ converges, and $\log_b (a/b^\delta) = \log_b a - \delta$. We conclude that $$ T(n) = n^{\log_b a} + \Theta(n^{\log_b a - \delta} n^\delta) = \Theta(n^{\log_b a}). $$ (So it is not quite true that the first term is dominant.)

Case 2. Suppose that $f(n) = n^{\log_b a}$ (this is the case $k = 0$; the case $k > 0$ is similar though slightly more complicated). Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^{\log_b a}. $$ This time $a = b^\delta$, and so each summand is equally dominant, leading to $$ T(n) = n^{\log_b a} + (\log_b n) n^{\log_b a} = \Theta(n^{\log_b a} \log n). $$

Case 3. Suppose that $f(n) = n^\delta$, where $\delta > \log_b a$. Then $$ T(n) = n^{\log_b a} + \sum_{i=0}^{\log_b n-1} \left(\frac{a}{b^\delta}\right)^i n^\delta. $$ Since $\delta > \log_b a$, we have $b^\delta > a$, and so $a/b^\delta < 1$. Therefore the geometric series $\sum_i (a/b^\delta)^i$ converges, implying that $$ T(n) = n^{\log_b a} + \Theta(n^\delta) = \Theta(n^\delta). $$

---

These proof sketches serve to explain that proof hints. However, they're not a complete proof, for two reasons. First, I assumed that $f$ has a specified form rather than a specified order of magnitude. Second, there is a tacit assumption that $n$ is a power of $b$. With more work we can take these points into account and prove the complete theorem. (A third and more minor point is the base case – you have assumed a base case of $1$, whereas the theorem calls for an arbitrary base case.)