Intuition behind the Master Theorem
You can use repeated substitution to obtain
$$
T(n) = f(n) + af(n/b) + a^2f(n/b^2) + \cdots
$$
Now suppose that $f(n) = n^\gamma$. Then
$$
\begin{align*}
T(n) &amp;= n^\gamma + a (n/b)^\gamma + a^2 (n/b^2)^\gamma + \cdots \\ &amp;=
n^\gamma \left[ 1 + \frac{a}{b^\gamma} + \left(\frac{a}{b^\gamma}\right)^2 + \cdots \right].
\end{align*}
$$

Let us assume that $n$ is a power of $b$, and that there is a base case $T(n) = C$ for some $C&gt;0$.

There are three different cases to consider:


If $a &lt; b^\gamma$ then the stuff in the brackets is a converging geometric series, and so $T(n) = \Theta(n^\gamma)$.
If $a = b^\gamma$ then all terms are the same. Since there are $\log_b n+1$ of them, $T(n) = \Theta(n^\gamma \log n)$.
If $a &gt; b^\gamma$ then the terms keeps increasing, and so we can approximate $T(n)$ by the last term, which is $a^{\log_b n} C = \Theta(n^{\log_b a})$.


The condition $a \lesseqqgtr b^\gamma$ is the same as $\log_b a \lesseqqgtr \gamma$, which is how the theorem is usually presented.

The actual theorem has some extra conditions that are needed in some of the cases when $f(n)$ is not a function of the exact form $n^\gamma$, but these are just technicalities.