Cases of Master Theorem

Suppose that we have $ \\ T(n)=\left\{\begin{matrix}
c, & \ \text{if } n

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

-
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

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?

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 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.)

StackExchange Computer Science Q#43347, answer score: 3