Intuition behind the Master Theorem

Question

The Master Theorem provides a method of solving recurrence relations for divide-and-conquer algorithms. It was first presented to me in my intro algorithms class as the following:

For a recurrence of the form $T(n) = aT(\frac{n}{b})+f(n)$ with constants $a \ge 1$ and $b>1$,

Case 1: if $f(n) = O(n^{\log_b(a-\varepsilon)})$ for some $\varepsilon > 0$, then $T(n) = \Theta(n^{\log_b(a)})$

Case 2: if $f(n) = \Theta(n^{\log_b(a)})$, then $T(n) = \Theta(\log n \cdot n^{\log _b(a)})$

Case 3: if $f(n) = \Omega(n^{log_b(a+\varepsilon)})$ for some $\varepsilon > 0$, and if $a f(\frac{n}{b}) \le c f(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

I have seen proofs of this theorem which go through the algebraic derivation of these results and I understand how to apply it but I don't have a very strong intuitive understanding of why it works. Here's what I understand so far, using these explanations of the Master Theorem on Quora as a starting point:

• The first answer frames the three cases in terms of the relative amount of work done at each level (either increasing geometrically, staying the same, or decreasing geometrically). At a high level, I understand this intuition and if the Master Theorem were given to me I could explain it using this reasoning, but I'm unconvinced that I could take this idea of geometric growth/decay and then derive the theorem.

• I think the second answer is closer to the kind of intuition I'm looking for. It explains the $aT(\frac{n}{b})$ term and the $f(n)$ term as opposing forces of replication and merging, respectively. However, I'm having trouble understanding how the intuitive cases (the replication step winning, the merging step winning, and the forces being equal) actually translate into the three different cases of the Master Theorem.

  This explanation also follows a similar argument and simplifies the Master Theorem in the following way:

  If $T(n) = aT(\frac{n}{b})+f(n)$ then compare $n^{\log_b a}$ with $f(n)$

  • If $f(n) < n^{\log_b a}$, then $T(n)=n^{\log_b a}$
  • If they are equal, then $T(n)=f(n)\log n$
  • If $f(n) > n^{\log_b a}$, then $T(n)=f(n)$

  While I see the connection with the Master Theorem cases here, there isn't an intuitive explanation for where the $n^{\log_b(a)}$ term comes from. That is, if I were just looking at the recurrence relation $T(n) = aT(\frac{n}{b})+f(n)$, how would I know to compare $f(n)$ with $n^{\log_b(a)}$? Perhaps there is some connection between $n^{\log_b(a)}$ and $aT(\frac{n}{b})$ that I'm missing?

In summary, I'm looking for something of the form "here is a high level concept/understanding (eg. geometric growth/decay, competing forces), and now here is how you can derive the Master Theorem from that idea." I would be satisfied with an explanation of how to get from the replication and merging intuition posed in the second bullet point above to the three different cases of the Master Theorem but I'm also interested in any other more intuitive perspectives.

Answer 1

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) &= n^\gamma + a (n/b)^\gamma + a^2 (n/b^2)^\gamma + \cdots \\ &= 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>0$.

There are three different cases to consider:

1. If $a < b^\gamma$ then the stuff in the brackets is a converging geometric series, and so $T(n) = \Theta(n^\gamma)$.

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

3. If $a > 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.