Recurrences and the Master Theorem

When an algorithm solves a problem by calling smaller copies of itself, its running time obeys an equation that refers to itself: the cost on an input of size $n$ is some local work plus the cost of the recursive calls on smaller inputs. Such an equation is a recurrence. Counting loops, as in the previous lesson, no longer suffices; we need techniques to turn a recurrence into a closed $\Theta$-bound. This lesson develops three, in increasing order of power and precision.

From a recursive algorithm to a recurrence

$\text{Divide-and-conquer}$ is the paradigm all three books use to introduce recurrences. It has three steps: divide the instance into subproblems, conquer them by recursion, and combine their solutions. Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves.

The $\text{Merge}$ subroutine walks the two sorted halves with two pointers, repeatedly copying the smaller front element into the output. It touches each of the $n$ elements a constant number of times, so it costs $\Theta (n)$.

Now read the cost off the structure. On an array of size $n$:

• Divide is computing the midpoint, $\Theta (1)$.
• Conquer is two recursive calls, each on $n/2$ elements, costing $2T(n/2)$.
• Combine is the merge, $\Theta (n)$.

Adding these (and noting that a one-element array is sorted at no cost) gives the recurrence

We can write this compactly, and as an inequality (since the combine step costs at most linear), as

and the bulk of the work is justifying that implication. This is the equation we must solve. (We freely write $n/2$ rather than $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$; the floors and ceilings change the answer by lower-order amounts that the asymptotics absorb. Skiena and CLRS both justify dropping them.¹) Throughout we also assume a constant base case, which lets us ignore the boundary condition when finding the asymptotic order.

Method 1: the recursion tree

The most intuitive method draws the recurrence. Each node is a subproblem labeled with the non-recursive work it does; its children are the subproblems it spawns. Summing all node labels gives $T(n)$.

For merge sort, the root does $cn$ work and has two children of size $n/2$. Each of those does $c(n/2)$ work and has two children of size $n/4$, and so on, until the leaves are size-$1$ subproblems.

The key observation: every level sums to $cn$. The root level is $cn$; the next level is $2\cdot c(n/2)=cn$; the level below is $4\cdot c(n/4)=cn$. The subproblem sizes shrink by half each level, so the tree has ${\log }_{2}n+1$ levels (from size $n$ down to size $1$), and the bottom level holds the $n$ size-$1$ leaves. Therefore

This is the result: merge sort runs in $\Theta (n\log n)$ time, strictly better than insertion sort's $\Theta (n^2)$.² The recursion tree also exposes why: the per-level work stays flat at $cn$ while the depth is only logarithmic.

The tree is a derivation, not yet a proof — it asks us to trust the level sums and the level count. When a recurrence is irregular (unequal splits, work that isn't a clean power of $n$), the tree still gives a reliable guess, which we then certify with the next method.

Method 2: substitution (guess and verify)

The substitution method is the rigorous one: guess the form of the answer, then prove it by induction on $n$. It is the only method that always works, and the only one that produces a complete proof.

We verify the guess $T(n)=O(n\log n)$ for the merge-sort recurrence $T(n)=2T(n/2)+cn$. We claim there is a constant $d>0$ with $T(n)\le dn{\log }_{2}n$ for all $n\ge 2$.

Inductive hypothesis. Assume the bound holds for all sizes smaller than $n$; in particular $T(n/2)\le d\frac{n}{2}{\log }_2\frac{n}{2}$.

Inductive step. Substitute into the recurrence:

This is $\le dn{\log }_{2}n$ exactly when $d\ge c$. So choosing any $d\ge c$ (and picking the base-case constant large enough to cover $n=2$) completes the induction. Hence $T(n)=O(n\log n)$.

A symmetric argument with the inequality reversed gives $T(n)=\Omega (n\log n)$, and together they yield $T(n)=\Theta (n\log n)$, confirming the tree.

Two warnings the books repeat:

• Guess the right form. Substitution verifies a guess; it cannot invent one. Use the recursion tree (or the Master Theorem below) to find the candidate.
• Beware the off-by-a-term trap. A guess like $T(n)\le dn$ for a $\Theta (n\log n)$ recurrence will seem to almost work but leave an unkillable residual term. Strengthening the hypothesis (subtracting a lower-order term, as in $T(n)\le dn\log n-bn$) is the standard fix.

A second example: counting inversions

A second divide-and-conquer problem makes the point sharply. Its recurrence has the same shape as merge sort but a different combine cost, and the combine cost is exactly the thing you must get right. An inversion of a list $⟨a_1,\dots ,a_n⟩$ is a pair $(i,j)$ with $i<j$ but $a_i>a_j$; the number of inversions measures how far from sorted the list is (a sorted list has $0$, a reversed list has $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$). The task: given $A[\mathrm{1..}n]$, return $\mathrm{ninv}(A)$.

The brute-force algorithm compares every pair and runs in $\Theta (n^2)$. To beat it, mimic merge sort: split $A$ in half, recursively count inversions inside each half, then count the cross inversions, the pairs with one element in the left half and one in the right. That gives a recurrence of the merge-sort form,

The three kinds of inversion partition cleanly along the split. On $A=⟨2,4,1,3⟩$, the inversions within each half are counted by recursion; the cross pairs, a left element greater than a right element, are exactly what the combine step must tally.

Counting cross inversions naively, with a double loop over the two halves, costs $\Theta (n^2)$, so the recurrence becomes $T(n)\le 2T(n/2)+b{n}^2$. Feed that to the recursion tree: the per-level work is now $b{n}^2,2\cdot b(n/2{)}^2=\frac{1}{2}b{n}^2,\dots$, which shrinks geometrically, so the root dominates and the tree sums to $\Theta (n^2)$. That is no improvement. The split bought us nothing because the combine step is as expensive as the brute force.

The lesson the recurrence teaches is therefore a demand: the combine step must run in $O(n)$, not $O(n^2)$. If we can count cross inversions in linear time, which one can, by counting them while merging the two sorted halves, the recurrence collapses to $T(n)\le 2T(n/2)+O(n)$, the merge-sort recurrence, and we get $\Theta (n\log n)$. The recurrence both predicts the running time and tells you precisely how fast the combine step has to be for divide-and-conquer to pay off.

Method 3: the Master Theorem

Merge sort's recurrence is one instance of a common pattern. The Master Theorem solves every recurrence of the form

where $a\ge 1$ and $b>1$ are constants and $f(n)$ is the divide-and-combine work. Here $a$ is the number of subproblems, $n/b$ is each subproblem's size, and $f(n)$ is the work done outside the recursion.

The theorem compares $f(n)$ against the watershed function$n^{{\log }_{b}a}$, the total cost of the leaves, which equals the number of leaves $a^{{\log }_{b}n}=n^{{\log }_{b}a}$ times the constant base-case cost. Which of the two dominates determines the answer.

The intuition matches the recursion tree. Compare the work at the root, $f(n)$, to the work at the leaves, $n^{{\log }_{b}a}$. In Case 1 the tree is leaf-heavy and the answer is the leaf count. In Case 3 the root work dwarfs everything below it and the answer is $f(n)$. In Case 2 the work is spread evenly across all $\Theta (\log n)$ levels, as we saw for merge sort, giving the extra $\log n$ factor.

Each panel stacks the per-level work from root (top) to leaves (bottom); the bar width is the work at that level. The case is decided by which end is heavier.

A caution from CLRS: the cases do not cover every recurrence.³ There are gaps. When $f$ is larger than the watershed but not polynomially larger (e.g. $f(n)=n^{{\log }_{b}a}\log n$), or when the regularity condition fails, the Master Theorem simply does not apply. Fall back to the recursion tree or substitution.

Worked examples

Example 1, merge sort. $T(n)=2T(n/2)+\Theta (n)$. Here $a=2$, $b=2$, so $n^{{\log }_{b}a}=n^{{\log }_{2}2}=n^1=n$. And $f(n)=\Theta (n)=\Theta (n^{{\log }_{b}a})$, which is Case 2. Therefore

recovering exactly what the tree and substitution gave.

Example 2, binary search.$T(n)=T(n/2)+\Theta (1)$: one subproblem of half size, constant work to pick the side. Here $a=1$, $b=2$, so $n^{{\log }_{2}1}=n^0=1$. Then $f(n)=\Theta (1)=\Theta (n^{{\log }_{b}a})$, Case 2 again, and

Example 3, leaf-dominated. $T(n)=4T(n/2)+n$. Now $a=4$, $b=2$, so $n^{{\log }_{2}4}=n^2$. The combine work $f(n)=n=O(n^{2-ϵ})$ (take $ϵ=1$) is polynomially smaller than the watershed, which is Case 1, so

The recursion has so many leaves ($n^2$ of them) that they dominate the modest linear work per level.

Example 4, root-dominated. $T(n)=2T(n/2)+n^2$. Here $a=2$, $b=2$, watershed $n^{{\log }_{2}2}=n$. The combine work $f(n)=n^2=\Omega (n^{1+ϵ})$ is polynomially larger, a Case 3 candidate. Check regularity: $af(n/b)=2(n/2{)}^2=\frac{1}{2}{n}^2=\frac{1}{2}f(n)\le kf(n)$ with $k=\frac{1}{2}<1$. Regularity holds, so

The root's quadratic work swamps the tree beneath it.

Choosing a method

The three methods are complementary, and Erickson in particular urges fluency with all of them:⁴

• Recursion tree: fastest for building intuition and guessing the answer; shows where the work concentrates.
• Master Theorem: fastest for getting the answer when the recurrence fits the $aT(n/b)+f(n)$ template; no derivation needed, but it has gaps.
• Substitution: the rigorous method that always works and produces a proof; use it to certify a guess, or when the other two do not apply (uneven splits, recurrences like $T(n)=T(n/3)+T(2n/3)+n$).

In practice: sketch the tree to guess, apply the Master Theorem if it fits, and reach for substitution whenever you need a guarantee rather than a hunch.

Takeaways

• A recursive algorithm induces a recurrence: $T(n)$ = local work + cost of recursive calls on smaller inputs. Merge sort gives $T(n)=2T(n/2)+\Theta (n)$.
• The recursion tree sums the per-node work; for merge sort every level costs $\Theta (n)$ across $\Theta (\log n)$ levels, giving $\Theta (n\log n)$.
• Substitution guesses the form and proves it by induction; it is the only always-applicable, fully rigorous method. Strengthen the hypothesis if a residual term blocks the step.
• The combine cost drives the answer. Counting inversions has the merge-sort shape $2T(n/2)+(\text{combine})$, but a naive $\Theta (n^2)$ combine gives $\Theta (n^2)$ overall, for no gain. Only a linear combine recovers $\Theta (n\log n)$.
• The Master Theorem solves $T(n)=aT(n/b)+f(n)$ by comparing $f(n)$ to the watershed $n^{{\log }_{b}a}$: leaves win (Case 1), they tie (Case 2, extra $\log n$), or the root wins (Case 3, needs regularity).
• The cases have gaps; when $f$ is only non-polynomially separated from the watershed, fall back to the tree or substitution.