Cases of Master Theorem Suppose that we have  $ \\ T(n)=\left\{\begin{matrix}
c, &amp; \ \text{if } n&lt;d\\ 
aT\left( \frac{n}{b} \right )+f(n), &amp; \ \ \text{if } n \geq d 
\end{matrix}\right.$

The Master theorem is the following:


If $f(n)=O(n^{\log_b a- \epsilon})$, then $T(n)= \Theta(n^{\log_ba})$
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&lt;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?
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 &lt; \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 &lt; \log_b a$, we have $b^\delta &lt; a$ and so $a/b^\delta &gt; 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 &gt; 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 &gt; \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 &gt; \log_b a$, we have $b^\delta &gt; a$, and so $a/b^\delta &lt; 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.)