The Master Method and it's Intuition

Most people learn the Master Method as a lookup table: compare $a$ to $b^d$ , pick one of three cases, done. The table works, but it's not understood; it's recited. The moment you meet a recurrence that doesn't fit neatly into the memorized shape, the table is useless.

The fix is to never memorize the table at all. Build a recursion tree for the general recurrence

$$T(n) = a \cdot T(n/b) + O(n^d)$$

count the work level by level, and let a single geometric series, built the exact way Tim Roughgarden derives it, tell you which of the three cases you're in and why. Once you've done this once by hand, the "three cases" stop feeling like three separate facts and become one picture viewed from three different angles.

Step 1: Build the tree, one level at a time

At the root (level 0), there is exactly one call, operating on an input of size $n$ , doing $O(n^d)$ work outside of its recursive calls.

Level 0:        [ n ]                work = n^d

That call makes $a$ recursive calls, each on a subproblem of size $n/b$ . That's level 1:

Level 0:            [ n ]                              work = n^d
Level 1:   [n/b] [n/b] ... [n/b]   (a of them)          work = a·(n/b)^d

The row work already tells you something important: going from level 0 to level 1, the work got multiplied by $a$ (more subproblems) and divided by $b^d$ (each subproblem cheaper). Whether the total work grows or shrinks as you go deeper depends entirely on which of those two effects is bigger.

Step 2: The general formula for row j

Generalize the pattern. At level $j$ (counting down from the root, which is level 0):

• Number of nodes: each node spawns $a$ children, so level $j$ has $a^j$ nodes.
• Size per node: the input has been divided by $b$ , $j$ times, so each node holds a subproblem of size $n/b^j$ .
• Work per node: $(n/b^j)^d$ .

Multiplying nodes by work-per-node gives the total work at level $j$ , call it $W_j$ :

$$W_j = a^j \cdot \left(\frac{n}{b^j}\right)^d = \frac{a^j \cdot n^d}{b^{jd}} = n^d \cdot \left(\frac{a}{b^d}\right)^j$$

Define $r = \dfrac{a}{b^d}$ . This single number is the ratio between consecutive rows of the tree: it is the whole Master Method compressed into one variable. $a$ is the rate at which subproblems multiply going down the tree; $b^d$ is the rate at which the work per subproblem shrinks. $r$ is simply which of those two effects wins.

Step 3: Total work is a geometric series

The tree bottoms out when a subproblem reaches size 1, i.e., when $n/b^j = 1$ , giving $j = \log_b n$ levels. Summing the row work over every level from the root to the leaves:

$$T(n) = \sum_{j=0}^{\log_b n} n^d \cdot r^j = n^d \sum_{j=0}^{k} r^j, \quad \text{where } k = \log_b n$$

This is exactly a geometric series, a sum of a constant ratio raised to increasing powers, and its behavior is fully determined by the closed-form geometric sum formula:

$$\sum_{j=0}^{k} r^j = \frac{r^{k+1} - 1}{r - 1} \quad (r \neq 1) \qquad \qquad \sum_{j=0}^{k} r^j = k+1 \quad (r = 1)$$

Everything from here is just plugging in $r = a/b^d$ and reading off what dominates.

Case 1: r is less than 1, the sum is bounded by a constant and dominated by the first term

If $a < b^d$ , then $r < 1$ . Rewrite the geometric sum for this case as:

$$\frac{r^{k+1} - 1}{r - 1} = \frac{1 - r^{k+1}}{1 - r}$$

Since $0 < r < 1$ , the term $r^{k+1}$ shrinks toward 0 as $k$ grows; it never grows, no matter how deep the tree is. The entire sum is therefore bounded above by the constant $\frac{1}{1-r}$ , regardless of how many levels the tree has. The geometric series doesn't blow up with depth. It converges, and the term that matters is the first term of the series (the root), because every later term is a shrinking fraction of it.

Level 0:  [ n ]           work = n^d
Level 1:  [n/b]           work = r · n^d
Level 2:  [n/b²]          work = r² · n^d
             ⋮                    ⋮  (shrinking geometrically)

Conclusion: since the sum is a constant multiple of the root's work, the total cost of the tree is dominated by the root, giving $T(n) = \Theta(n^d)$ .

Case 2: r equals 1, every term is equal and the sum is just the level count

If $a = b^d$ , then $r = 1$ , and the geometric sum formula degenerates to $k+1$ , the number of levels. Every row contributes exactly $n^d$ , with no growth and no decay:

Level 0:  [ n ]              work = n^d
Level 1:  [n/b] ... [n/b]    work = n^d
Level 2:  [n/b²] ... [n/b²]  work = n^d
             ⋮                  ⋮  (flat)

Conclusion: since there are $\log_b n + 1$ levels, each contributing $n^d$ , the total is $T(n) = \Theta(n^d \log n)$ .

Case 3: r is greater than 1, the sum is dominated by the last term

If $a > b^d$ , then $r > 1$ . Now the geometric sum

$$\frac{r^{k+1} - 1}{r - 1}$$

grows without bound as $k$ grows. Crucially, it is dominated by its largest term, which is the final term of the series, $r^k$ , not the first one. This is the mirror image of Case 1: when $r > 1$ , each successive term is larger than the one before it by a factor of $r$ , so the sum is within a constant factor of its biggest term. Pulling $r^k$ out of every term in the sum:

$$\sum_{j=0}^{k} r^j = r^k \sum_{i=0}^{k} \left(\frac{1}{r}\right)^i = O(r^k)$$

since $\frac{1}{r} < 1$ , that inner sum falls back into Case 1's bounded regime: it's just some constant. So the total work is dominated by the last level of the tree, the leaves, not the root.

Level 0:  [ n ]                    work = n^d
Level 1:  [n/b] [n/b] [n/b] [n/b]  work = r · n^d
Level 2:  [n/b²] × a²              work = r² · n^d
             ⋮                        ⋮  (growing geometrically)
Level k:  [1] × a^k                work = r^k · n^d   ← dominant term

Don't leave that dominant term as $r^k \cdot n^d$ ; simplify it all the way down. Recall $k = \log_b n$ , which means $b^k = n$ . Substitute $r = a/b^d$ and expand step by step:

$$r^k \cdot n^d = \left(\frac{a}{b^d}\right)^k \cdot n^d = \frac{a^k}{(b^k)^d} \cdot n^d = a^k \cdot \left(\frac{n}{b^k}\right)^d$$

Now use $b^k = n$ to collapse the fraction:

$$a^k \cdot \left(\frac{n}{b^k}\right)^d = a^k \cdot \left(\frac{n}{n}\right)^d = a^k \cdot 1^d = a^k$$

So the dominant term is just $a^k$ , plain and simple: the number of leaves. Substituting $k = \log_b n$ back in, and using the identity that swapping the base and the exponent of a power-of-a-log leaves the value unchanged,

$$a^k = a^{\log_b n} = n^{\log_b a}$$

Conclusion: since the sum is dominated by the leaf level, and that leaf-level term simplifies to exactly $a^k = n^{\log_b a}$ , $T(n) = \Theta!\left(n^{\log_b a}\right)$ .

Why that exponent is exactly the leaf count

That final expression, $n^{\log_b a}$ , isn't an arbitrary algebra trick. It is, literally, the number of leaves in the tree. The derivation above showed exactly that: the dominant term collapsed to $a^k$ , the leaf count, and rewriting $k$ as $\log_b n$ turned that leaf count into $n^{\log_b a}$ .

So in Case 3, when the tree's total cost is dominated by its bottom row, what you're really computing is "how many leaves does this tree have?", and the answer to that question, $n^{\log_b a}$ , is the running time. The formula isn't describing some abstract growth rate. It's counting boxes at the bottom of the picture you already drew.

Worked example: fixing b and d, varying only a

To see all three cases as one continuous family, fix $b = 2$ and $d = 1$ (so the base recurrence is $T(n) = a \cdot T(n/2) + O(n)$ ) and vary only $a$ .

$a = 1 \Rightarrow r = \tfrac{1}{2} < 1$ . $T(n) = T(n/2) + O(n)$ . Row work shrinks geometrically: $n, n/2, n/4, \dots$ . Bounded by the root. $T(n) = \Theta(n)$ .

$a = 2 \Rightarrow r = 1$ . $T(n) = 2T(n/2) + O(n)$ , merge sort. Row work is flat: $n, n, n, \dots$ across $\log_2 n$ levels. $T(n) = \Theta(n \log n)$ .

$a = 4 \Rightarrow r = 2 > 1$ . $T(n) = 4T(n/2) + O(n)$ . Row work grows geometrically: $n, 2n, 4n, \dots$ , dominated by the leaves. Leaf count is $4^{\log_2 n} = n^{\log_2 4} = n^2$ . $T(n) = \Theta(n^2)$ .

Same $b$ , same $d$ , same tree-building process; only the value of $r$ changed, and the geometric series formula did the rest of the work.

The cheat sheet, now with the reasoning attached

Compare	Ratio	Geometric sum behavior	Dominant term	Total cost
$\log_b a < d$	$r < 1$	bounded by a constant	first term (the root)	$\Theta(n^d)$
$\log_b a = d$	$r = 1$	exactly $k+1$ equal terms	every level equally	$\Theta(n^d \log n)$
$\log_b a > d$	$r > 1$	grows; dominated by $r^k$	last term (the leaves)	$\Theta(n^{\log_b a})$ , i.e. the leaf count

The "compare $\log_b a$ to $d$ " rule isn't three unrelated facts to memorize. It's one geometric series, the sum of $r^j$ , being read in the only three ways a geometric series can behave: shrinking to a constant, staying flat, or exploding toward its final term. And in that last, exploding case, the scary-looking exponent $n^{\log_b a}$ is nothing more than the plain count of leaves at the bottom of the tree. Once that's internalized, no recurrence outside the textbook table needs to be scary again. Draw three rows, work out $r$ , and the geometric sum formula tells you exactly where the weight of the tree sits.