---
title: Recurrences and the Master Theorem
module: Foundations
moduleNumber: 1
lessonNumber: 5
order: 105
summary: >
  Recursive and divide-and-conquer algorithms describe their own running time
  with a recurrence: $T(n)$ in terms of $T$ on smaller inputs. We solve
  recurrences three ways — drawing the recursion tree, guessing-and-verifying by
  induction, and applying the Master Theorem — using merge sort as the running
  example, then handle unequal splits with Akra–Bazzi.
topics: [Recurrences]
sources:
  - book: CLRS
    ref: "Ch. 4 — Divide-and-Conquer"
  - book: Skiena
    ref: "§2.7–2.10 — Logarithms, Recurrences, Divide-and-Conquer"
  - book: Erickson
    ref: "Ch. 1–2 — Recursion; Backtracking & Divide-and-Conquer"
practice:
  - title: 'Sqrt(x)'
    slug: sqrtx
    difficulty: Easy
  - title: 'Pow(x, n)'
    slug: powx-n
    difficulty: Medium
  - title: 'Search in Rotated Sorted Array'
    slug: search-in-rotated-sorted-array
    difficulty: Medium
  - title: 'Different Ways to Add Parentheses'
    slug: different-ways-to-add-parentheses
    difficulty: Medium
---

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](/algorithms/foundations/asymptotic-analysis), 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, and closes with the
Akra–Bazzi method for the uneven splits the Master Theorem cannot handle.

## From a recursive algorithm to a recurrence

$\textsc{Divide-and-conquer}$ is the paradigm CLRS, Skiena, and Erickson all use
to introduce recurrences. It has three steps: **divide** the instance into subproblems,
**conquer** them by recursion, and **combine** their solutions. [**Merge sort**](/algorithms/divide-and-conquer/mergesort)
splits the array in half, sorts each half recursively, and merges the two sorted
halves.

```algorithm
caption: $\textsc{Merge-Sort}(A, p, r)$ — sort $A[p..r]$
number: 1
if $p < r$ then
  $q \gets \floor{(p + r) / 2}$ // midpoint
  call $\textsc{Merge-Sort}(A, p, q)$ // sort left half
  call $\textsc{Merge-Sort}(A, q+1, r)$ // sort right half
  call $\textsc{Merge}(A, p, q, r)$ // combine halves
return $A$
```

The $\textsc{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 $2\,T(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

$$
T(n) =
\begin{cases}
\Theta(1) & \text{if } n = 1, \\[2pt]
2\,T(n/2) + \Theta(n) & \text{if } n > 1.
\end{cases}
$$

We can write this compactly, and as an _inequality_ (since the
combine step costs _at most_ linear), as
$$
T(n) \le 2\,T(n/2) + O(n) \;\Longrightarrow\; T(n) = O(n\log n),
$$
and the bulk of the work is justifying that implication. This is the equation we
must solve. (We freely write $n/2$ rather than
$\floor{n/2}$ and $\ceil{n/2}$; the floors and ceilings change the answer by
lower-order amounts that the asymptotics absorb. Skiena and CLRS both justify
dropping them.[^skiena-floors]) 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.

$$
% caption: Recursion tree for merge sort, $T(n) = 2\,T(n/2) + cn$. The right-hand column
%          sums each level: $2^i$ nodes of size $n/2^i$, each doing $c\,n/2^i$ work, give
%          $2^i \cdot c\,n/2^i = cn$ at every level.
\begin{tikzpicture}[
  every node/.style={draw, minimum size=6mm, inner sep=2pt},
  node distance=8mm and 4mm]
  \definecolor{acc}{HTML}{2348F2}
  % level 0
  \node (r) {$cn$};
  % level 1
  \node (a) [below left=12mm and 16mm of r] {$c\tfrac{n}{2}$};
  \node (b) [below right=12mm and 16mm of r] {$c\tfrac{n}{2}$};
  % level 2
  \node (a1) [below left=12mm and 4mm of a] {$c\tfrac{n}{4}$};
  \node (a2) [below right=12mm and 4mm of a] {$c\tfrac{n}{4}$};
  \node (b1) [below left=12mm and 4mm of b] {$c\tfrac{n}{4}$};
  \node (b2) [below right=12mm and 4mm of b] {$c\tfrac{n}{4}$};
  \draw (r) -- (a); \draw (r) -- (b);
  \draw (a) -- (a1); \draw (a) -- (a2);
  \draw (b) -- (b1); \draw (b) -- (b2);
  % per-level sums in a right-hand column
  \node[draw=none, black] at ($(r) + (5.2,0.9)$) {level sum};
  \node[draw=none, text=acc] at ($(r) + (5.2,0)$) {$cn$};
  \node[draw=none, text=acc] at ($(b) + (3.4,0)$) {$2\,c\tfrac{n}{2} = cn$};
  \node[draw=none, text=acc] at ($(b2) + (2.4,0)$) {$4\,c\tfrac{n}{4} = cn$};
  \node[draw=none, text=acc] at ($(b2) + (2.4,-1.0)$) {$\vdots$};
  \node[draw=none] at ($(b2) + (-3.0,-1.0)$) {$\vdots$};
\end{tikzpicture}
$$

**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

$$
T(n) = \underbrace{cn}_{\text{per level}} \times \underbrace{(\log_2 n + 1)}_{\text{levels}}
= cn \log_2 n + cn = \Theta(n \log n).
$$

This is the result: **merge sort runs in $\Theta(n \log n)$ time**,
strictly better than insertion sort's $\Theta(n^2)$.[^clrs-tree] 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.

::impl{algo="recurrence_tree"}

## 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) = 2\,T(n/2) + cn$.

> **Claim.** There is a constant $d > 0$ with $T(n) \le d\,n \log_2 n$ for all
> $n \ge 2$.

> **Proof.** By induction on $n$.
>
> **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:
> $$
> \begin{aligned}
> T(n) &= 2\,T(n/2) + cn \\
> &\le 2\parens{d\,\tfrac{n}{2}\log_2\tfrac{n}{2}} + cn \\
> &= d\,n\,(\log_2 n - 1) + cn \\
> &= d\,n\log_2 n - dn + cn \\
> &= d\,n\log_2 n - (d - c)\,n.
> \end{aligned}
> $$
> This is $\le d\,n\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)$. $\qed$

$$
% caption: The substitution method: assume the bound on smaller inputs, substitute into
%          the recurrence, and check that the leftover residual term lets the same bound
%          re-emerge for $n$.
\begin{tikzpicture}[
  box/.style={draw, align=center, inner sep=4pt, minimum height=10mm},
  node distance=6mm,
  >={Stealth[length=2.5mm]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=acc!15] (h) {assume\\$T(\tfrac{n}{2})$ at most $d\,\tfrac{n}{2}\log\tfrac{n}{2}$};
  \node[box, right=14mm of h] (s) {substitute into\\$T(n) = 2\,T(\tfrac{n}{2}) + cn$};
  \node[box, fill=acc!15, right=14mm of s] (c) {conclude\\$T(n)$ at most $d\,n\log n$};
  \draw[->] (h) -- (s);
  \draw[->] (s) -- (c);
  \node[box, fill=red!16, below=10mm of s, align=center] (r) {leftover $cn$ absorbed\\exactly when d $\ge$ c};
  \draw[->] (s) -- (r);
  \draw[->] (r) -- (c);
\end{tikzpicture}
$$

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 standard references 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.
- **Land on the exact bound.** The inductive step must end at the _same_
  inequality it assumed, with the _same_ constant. "Close enough plus a
  lower-order term" is not a proof, as the next example shows.

### A failing guess, and why it fails

Watch the method reject a wrong answer. Take the same recurrence,
$T(n) = 2\,T(n/2) + n$, and guess $T(n) = O(n)$; concretely, try to prove
$T(n) \le cn$ for some constant $c > 0$. Substitute the hypothesis
$T(n/2) \le c\,\tfrac{n}{2}$:

$$
T(n) \;=\; 2\,T(n/2) + n \;\le\; 2\parens{c\,\tfrac{n}{2}} + n \;=\; cn + n.
$$

It is tempting to declare victory here: "$cn + n = O(n)$, so we are
done." That reasoning is circular hand-waving, and CLRS singles it out as the
classic substitution error.[^clrs-subst] The induction committed to the exact
statement $T(n) \le cn$ with one fixed constant $c$ that works for _every_ $n$.
The step must therefore arrive at $\le cn$ on the nose, and

$$
cn + n \;\le\; cn \quad\Longleftrightarrow\quad n \le 0,
$$

which never holds. No choice of $c$, however large, absorbs the leftover $+n$;
making $c$ bigger inflates both sides equally. The induction is stuck, and it is
stuck for a good reason: the claim is false. We already know
$T(n) = \Theta(n\log n)$, which is not $O(n)$. The failed algebra is the method
working as designed — a wrong guess leaves a residual that cannot be paid for.

$$
% caption: Anatomy of a failed guess for $T(n) = 2\,T(n/2) + n$. Guessing $T(n) \le cn$
%          leaves a $+n$ residual that no constant absorbs; the escape is a stronger
%          hypothesis: raise the guess's order, or subtract a lower-order term.
\begin{tikzpicture}[
  box/.style={draw, align=center, inner sep=4pt, minimum height=10mm},
  node distance=6mm,
  >={Stealth[length=2.5mm]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box, fill=acc!15] (g) {guess\\$T(n)$ at most $cn$};
  \node[box, right=12mm of g] (s) {substitute:\\$T(n)$ at most $2c\tfrac{n}{2} + n = cn + n$};
  \node[box, fill=red!16, right=12mm of s] (f) {leftover $+n$ never\\absorbed: step fails};
  \draw[->] (g) -- (s);
  \draw[->] (s) -- (f);
  \node[box, fill=acc!15, below=9mm of s] (fix) {strengthen the hypothesis: raise the order to $d\,n\log n$,\\or subtract a lower-order term};
  \draw[->] (f.south) |- (fix.east);
\end{tikzpicture}
$$

The escape is to strengthen the guess. For this recurrence the honest fix is to
raise its order to $T(n) \le d\,n\log_2 n$, reproducing the proof carried
out above: the substitution then produces the residual $-(d - c)\,n$, which is
_negative_ for $d \ge c$ and absorbs the linear term.

### Strengthening by subtracting a lower-order term

A subtler failure mode: the guess has the _right_ order and still gets stuck.
Consider

$$
T(n) = 2\,T(\floor{n/2}) + 1.
$$

The tree says $\Theta(n)$: the per-level work is $1, 2, 4, \dots$, a geometric
series dominated by its last term, the $n$ leaves. So guess $T(n) \le cn$ and
substitute:

$$
T(n) \;\le\; 2\parens{c\floor{n/2}} + 1 \;\le\; cn + 1.
$$

Off by $+1$ — and no constant $c$ kills a leftover that survives every doubling
of $c$, for the same reason as before. Yet the guess's _order_ is correct. The
fix, which CLRS presents with this exact recurrence, is counterintuitive:
_strengthen_ the claim by subtracting a lower-order term.[^clrs-subst] Guess

$$
T(n) \;\le\; cn - d \qquad \text{for constants } c > 0,\ d \ge 0.
$$

Substituting the stronger hypothesis on $\floor{n/2}$:

$$
T(n) \;\le\; 2\parens{c\floor{n/2} - d} + 1 \;\le\; cn - 2d + 1
\;=\; (cn - d) - (d - 1) \;\le\; cn - d
$$

whenever $d \ge 1$. Choosing $d = 1$ (and $c$ large enough to cover the base
case) completes the induction. The stronger hypothesis _helps_ rather than
hurts because it is assumed on the subproblems too: each of the two recursive
calls brings a $-d$ credit, and the two credits pay for the $+1$ of local work
with one $-d$ to spare. Proving less was impossible; proving more is easy.

::impl{algo="substitution_method"}

## 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 the thing you must get right. An **inversion**
of a list $\langle a_1,\dots,a_n\rangle$ 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 $\binom{n}{2}$). The task: given
$A[1..n]$, return $\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,

$$
T(n) \le 2\,T(n/2) + (\text{cost of counting cross inversions}).
$$

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

$$
% caption: Cross inversions on $\langle 2,4,1,3\rangle$ split into halves
%          $\langle 2,4\rangle$ and $\langle 1,3\rangle$. Each red arc is a cross
%          inversion (a left element bigger than a right one): $(2,1),(4,1),(4,3)$.
%          Within-half inversions are handled by recursion; the combine step counts only
%          these crossing pairs.
\begin{tikzpicture}[
    cell/.style={draw, minimum size=8mm, font=\small},
    lbl/.style={font=\footnotesize},
    >={Stealth[length=2.2mm]}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.6,-2.1) rectangle (5.9,1.3);
  % left half
  \node[cell, fill=acc!15] (L1) at (0,0) {2};
  \node[cell, fill=acc!15, right=0mm of L1] (L2) {4};
  % gap, then right half
  \node[cell, right=8mm of L2] (R1) {1};
  \node[cell, right=0mm of R1] (R2) {3};
  \node[lbl, above=1mm of L1.north west, anchor=south west] {left half};
  \node[lbl, above=1mm of R2.north east, anchor=south east] {righ\/t half};
  \draw[dashed, black] ($(L2.north east)+(0.4,0.55)$) -- ($(L2.south east)+(0.4,-0.95)$);
  % cross inversions: one red arc per inverted pair, nested in separate depth lanes
  % and fanned at the shared cells (4 and 1) so no two tails or arrowheads stack
  \draw[->, red!70!black, semithick]
    ($(L2.south)+(-0.09,0)$) .. controls +(0,-0.5) and +(0,-0.5) .. ($(R1.south)+(0.18,0)$); % (4>1)
  \draw[->, red!70!black, semithick]
    (L1.south) .. controls +(0,-0.92) and +(0,-0.92) .. ($(R1.south)+(-0.18,0)$); % (2>1)
  \draw[->, red!70!black, semithick]
    ($(L2.south)+(0.09,0)$) .. controls +(0,-1.3) and +(0,-1.3) .. (R2.south); % (4>3)
  \node[lbl, red!75!black, align=center] at (2.65,-1.95) {$3$ cross inversions: $(2{>}1)$, $(4{>}1)$, $(4{>}3)$};
\end{tikzpicture}
$$

Counting cross inversions _naively_, with a double loop over the two halves, costs
$\Theta(n^2)$, so the recurrence becomes $T(n) \le 2\,T(n/2) + bn^2$. Feed that to
the recursion tree: the per-level work is now $b\,n^2,\ 2\cdot b(n/2)^2 =
\tfrac12 bn^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.

$$
% caption: Naive counting-inversions tree, $T(n) = 2\,T(n/2) + bn^2$: unlike merge
%          sort's flat tree, the level sums $bn^2, \tfrac12 bn^2, \tfrac14 bn^2, \dots$
%          shrink geometrically, so the root dominates and the total is $\Theta(n^2)$.
\begin{tikzpicture}[
  every node/.style={draw, minimum size=6mm, inner sep=2pt},
  node distance=8mm and 4mm]
  \definecolor{acc}{HTML}{2348F2}
  % level 0
  \node[fill=acc!15] (r) {$bn^2$};
  % level 1
  \node (a) [below left=12mm and 16mm of r] {$b(\tfrac{n}{2})^2$};
  \node (b) [below right=12mm and 16mm of r] {$b(\tfrac{n}{2})^2$};
  % level 2
  \node (a1) [below left=12mm and 4mm of a] {$b(\tfrac{n}{4})^2$};
  \node (a2) [below right=12mm and 4mm of a] {$b(\tfrac{n}{4})^2$};
  \node (b1) [below left=12mm and 4mm of b] {$b(\tfrac{n}{4})^2$};
  \node (b2) [below right=12mm and 4mm of b] {$b(\tfrac{n}{4})^2$};
  \draw (r) -- (a); \draw (r) -- (b);
  \draw (a) -- (a1); \draw (a) -- (a2);
  \draw (b) -- (b1); \draw (b) -- (b2);
  % per-level sums in a right-hand column
  \node[draw=none, black] at ($(r) + (6.0,0.9)$) {level sum};
  \node[draw=none, text=acc] at ($(r) + (6.0,0)$) {$bn^2$};
  \node[draw=none, text=acc] at ($(b) + (3.7,0)$) {$\tfrac12 bn^2$};
  \node[draw=none, text=acc] at ($(b2) + (2.6,0)$) {$\tfrac14 bn^2$};
  \node[draw=none, text=acc] at ($(b2) + (2.6,-1.0)$) {$\vdots$};
  \node[draw=none] at ($(b2) + (-3.0,-1.0)$) {$\vdots$};
\end{tikzpicture}
$$

The recurrence therefore sets a requirement: 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 2\,T(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

$$
T(n) = a\,T(n/b) + f(n),
$$

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.

$$
% caption: The Master Theorem weighs the root's combine work $f(n)$ against the leaves'
%          total cost, the watershed $n^{\log_b a}$: each leaf costs $\Theta(1)$, and
%          there are $n^{\log_b a}$ of them.
\begin{tikzpicture}[
  every node/.style={draw, minimum size=6mm, inner sep=2pt},
  node distance=8mm and 4mm]
  \definecolor{acc}{HTML}{2348F2}
  % root
  \node[fill=acc!15] (r) {$f(n)$};
  % level 1
  \node (a) [below left=11mm and 14mm of r] {$f(\tfrac{n}{b})$};
  \node (b) [below right=11mm and 14mm of r] {$f(\tfrac{n}{b})$};
  \node[draw=none] (dots) [below=2mm of r, yshift=-9mm] {...};
  % leaves
  \node[fill=black!8] (l1) [below=20mm of a] {leaf};
  \node[fill=black!8] (l2) [below=20mm of b] {leaf};
  \node[draw=none] (ldots) at ($(l1)!0.5!(l2)$) {...};
  \draw (r) -- (a); \draw (r) -- (b);
  \draw[dashed] (a) -- (l1); \draw[dashed] (b) -- (l2);
  % annotations
  \node[draw=none, right=3mm of r, align=left] {root work $= f(n)$};
  \node[draw=none, below=4mm of ldots, align=center] {$n^{\log_b a}$ leaves, so the leaf level costs $n^{\log_b a}$};
\end{tikzpicture}
$$

> **Theorem (Master).** Let $T(n) = a\,T(n/b) + f(n)$ with $a \ge 1$, $b > 1$.
> Let $\epsilon > 0$ be a constant. Then:
>
> **Case 1 (leaves dominate).** If $f(n) = O\!\parens{n^{\log_b a - \epsilon}}$
> (that is, $f$ is _polynomially smaller_ than the watershed), then
> $$T(n) = \Theta\!\parens{n^{\log_b a}}.$$
>
> **Case 2 (balanced).** If $f(n) = \Theta\!\parens{n^{\log_b a}}$ ($f$
> matches the watershed), then
> $$T(n) = \Theta\!\parens{n^{\log_b a}\,\log n}.$$
>
> **Case 3 (root dominates).** If $f(n) = \Omega\!\parens{n^{\log_b a + \epsilon}}$
> ($f$ is _polynomially larger_ than the watershed) and the **regularity
> condition** $a\,f(n/b) \le k\,f(n)$ holds for some constant $k < 1$ and all
> large $n$, then
> $$T(n) = \Theta\!\parens{f(n)}.$$

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.

$$
% caption: Where the work concentrates in the Master Theorem's three cases. The answers,
%          left to right: $\Theta(n^{\log_b a})$, $\Theta(n^{\log_b a}\log n)$, and
%          $\Theta(f(n))$.
\begin{tikzpicture}[scale=1.0]
  \definecolor{acc}{HTML}{2348F2}
  \def\bar#1#2#3{\filldraw[acc!75,draw=acc] ({#1-#3/2},{#2}) rectangle ({#1+#3/2},{#2+0.4});}
  \bar{0}{0}{0.5} \bar{0}{-0.52}{0.9} \bar{0}{-1.04}{1.5} \bar{0}{-1.56}{2.4}
  \bar{4.3}{0}{1.5} \bar{4.3}{-0.52}{1.5} \bar{4.3}{-1.04}{1.5} \bar{4.3}{-1.56}{1.5}
  \bar{8.6}{0}{2.4} \bar{8.6}{-0.52}{1.5} \bar{8.6}{-1.04}{0.9} \bar{8.6}{-1.56}{0.5}
  \node[font=\small\bfseries] at (0,0.75) {Case 1};
  \node[font=\small\bfseries] at (4.3,0.75) {Case 2};
  \node[font=\small\bfseries] at (8.6,0.75) {Case 3};
  \node[font=\footnotesize] at (0,-2.5) {leaves dominate};
  \node[font=\footnotesize] at (4.3,-2.5) {every level equal};
  \node[font=\footnotesize] at (8.6,-2.5) {root dominates};
  \node[font=\footnotesize] at (0,-3.05) {answer: $n^{\log_b a}$};
  \node[font=\footnotesize] at (4.3,-3.05) {answer: $n^{\log_b a}\log n$};
  \node[font=\footnotesize] at (8.6,-3.05) {answer: $f(n)$};
\end{tikzpicture}
$$

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.

### Why the cases hold: three trees

The theorem is a statement about geometric series, and the recursion tree makes
the series visible.[^clrs-master] Unroll $T(n) = a\,T(n/b) + f(n)$: level $i$ of
the tree holds $a^i$ subproblems of size $n/b^i$, each contributing $f(n/b^i)$
of non-recursive work, so

$$
\text{level-}i\text{ sum} \;=\; a^i\,f\!\parens{n/b^i},
\qquad i = 0, 1, \dots, \log_b n - 1,
$$

and the leaf level contributes $\Theta(n^{\log_b a})$. Summing,

$$
T(n) \;=\; \sum_{i=0}^{\log_b n - 1} a^i\,f\!\parens{\frac{n}{b^i}}
\;+\; \Theta\!\parens{n^{\log_b a}}.
$$

When $f(n) = \Theta(n^d)$ is a polynomial, the level sums take a clean form:

$$
a^i \parens{\frac{n}{b^i}}^{\!d} = n^d \parens{\frac{a}{b^d}}^{\!i},
$$

a geometric series with ratio $r = a/b^d$. Everything reduces to whether $r$ is
above, at, or below $1$ — equivalently, whether $d$ is below, at, or above
$\log_b a$. Skiena states the theorem in exactly this three-way form.[^skiena-master]

**Case 1, leaves dominate ($r > 1$).** Take $T(n) = 4\,T(n/2) + cn$: here
$a = 4$, $b = 2$, $d = 1$, so $r = 4/2^1 = 2$. Reading the tree level by level:

$$
\begin{aligned}
\text{level } 0 &: cn \\
\text{level } 1 &: 4 \cdot c\tfrac{n}{2} = 2cn \\
\text{level } 2 &: 16 \cdot c\tfrac{n}{4} = 4cn \\
\text{level } i &: 4^i \cdot c\tfrac{n}{2^i} = 2^i\,cn,
\end{aligned}
$$

doubling every level. A growing geometric series is dominated by its _last_
term, so the total is within a constant factor of the bottom:

$$
\sum_{i=0}^{\log_2 n - 1} 2^i\,cn \;=\; cn\,(2^{\log_2 n} - 1) \;=\; cn\,(n - 1)
\;=\; \Theta(n^2),
$$

which matches the leaf level: $4^{\log_2 n} = n^{\log_2 4} = n^2$ leaves at
$\Theta(1)$ each. The combine work is irrelevant; the answer is the leaf count,
$T(n) = \Theta(n^{\log_b a}) = \Theta(n^2)$.

$$
% caption: Case 1 tree for $T(n) = 4\,T(n/2) + cn$. Each node spawns four children of
%          half the size, so the level sums $cn, 2cn, 4cn, \dots$ double all the way
%          down; the growing geometric series is dominated by its last term, the
%          $n^{\log_2 4} = n^2$ leaves. Total: $\Theta(n^2)$.
\begin{tikzpicture}[
  every node/.style={draw, minimum size=6mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % level 0
  \node (r) at (0,0) {$cn$};
  % level 1: four children of size n/2
  \node (a) at (-3.6,-1.6) {$c\tfrac{n}{2}$};
  \node (b) at (-1.2,-1.6) {$c\tfrac{n}{2}$};
  \node (c) at (1.2,-1.6) {$c\tfrac{n}{2}$};
  \node (d) at (3.6,-1.6) {$c\tfrac{n}{2}$};
  \draw (r) -- (a); \draw (r) -- (b); \draw (r) -- (c); \draw (r) -- (d);
  % each child spawns four more: fading stubs
  \foreach \p in {a,b,c,d} {
    \draw[black] (\p.south) -- ($(\p.south)+(-0.45,-0.5)$);
    \draw[black] (\p.south) -- ($(\p.south)+(-0.15,-0.5)$);
    \draw[black] (\p.south) -- ($(\p.south)+(0.15,-0.5)$);
    \draw[black] (\p.south) -- ($(\p.south)+(0.45,-0.5)$);
  }
  \node[draw=none] at (0,-2.9) {$\vdots$};
  % leaf strip
  \node[fill=black!8, minimum width=84mm] (leaves) at (0,-3.9) {$n^2$ leaves of size $1$};
  % per-level sums in a right-hand column
  \node[draw=none, black] at (6.6,0.9) {level sum};
  \node[draw=none, text=acc] at (6.6,0) {$cn$};
  \node[draw=none, text=acc] at (6.6,-1.6) {$4\,c\tfrac{n}{2} = 2cn$};
  \node[draw=none, text=acc] at (6.6,-2.9) {level i: $2^i\,cn$};
  \node[draw=none, text=acc] at (6.6,-3.9) {$c\,n^2$};
\end{tikzpicture}
$$

**Case 2, balanced ($r = 1$).** Merge sort, $T(n) = 2\,T(n/2) + cn$: $a = 2$,
$b = 2$, $d = 1$, so $r = 2/2^1 = 1$. This is the first tree we drew. The level
sums are

$$
cn,\quad 2 \cdot c\tfrac{n}{2} = cn,\quad 4 \cdot c\tfrac{n}{4} = cn,\quad \dots
$$

— constant at $cn$ for all $\log_2 n + 1$ levels. A flat series is just
(number of terms) $\times$ (term), so

$$
T(n) \;=\; cn \cdot (\log_2 n + 1) \;=\; \Theta(n\log n)
\;=\; \Theta\!\parens{n^{\log_b a}\log n}.
$$

Neither end of the tree wins; the $\log n$ factor is the number of levels, each
pulling equal weight.

**Case 3, root dominates ($r < 1$).** The naive inversion-counting tree,
$T(n) = 2\,T(n/2) + bn^2$: $a = 2$, $b = 2$, $d = 2$, so $r = 2/2^2 = \tfrac12$.
The level sums

$$
bn^2,\quad 2 \cdot b\parens{\tfrac{n}{2}}^2 = \tfrac12 bn^2,\quad
4 \cdot b\parens{\tfrac{n}{4}}^2 = \tfrac14 bn^2,\quad \dots
$$

halve every level. A shrinking geometric series is dominated by its _first_
term and bounded by a constant multiple of it:

$$
\sum_{i \ge 0} \parens{\tfrac12}^{\!i} bn^2 \;\le\; 2\,bn^2,
$$

so $T(n) = \Theta(f(n)) = \Theta(n^2)$. The root alone already costs $bn^2$;
the entire tree below it costs at most as much again.

> **Takeaway.** For $T(n) = a\,T(n/b) + \Theta(n^d)$, compare the level-sum
> ratio $r = a/b^d$ to $1$: if $r > 1$ the series grows and the leaves win
> ($\Theta(n^{\log_b a})$); if $r = 1$ every level ties
> ($\Theta(n^d \log n)$); if $r < 1$ the series shrinks and the root wins
> ($\Theta(n^d)$). One division decides the case.

The ratio test doubles as a sanity check on concrete instances. For
$T(n) = 8\,T(n/2) + n^2$: $r = 8/2^2 = 2 > 1$, Case 1, answer
$\Theta(n^{\log_2 8}) = \Theta(n^3)$. For $T(n) = 2\,T(n/2) + n$: $r = 2/2 = 1$,
Case 2, $\Theta(n\log n)$. For $T(n) = 2\,T(n/2) + n^2$: $r = 2/4 = \tfrac12 < 1$,
Case 3, $\Theta(n^2)$.

### Regularity and the gaps between the cases

Two fine-print clauses matter in practice.

**The regularity condition.** Case 3 additionally demands
$a\,f(n/b) \le k\,f(n)$ for some constant $k < 1$: the combine work one level
down must be a constant factor _smaller_, which is precisely what makes the
level sums a shrinking geometric series. For any polynomial $f$ that satisfies
Case 3's growth bound the condition holds automatically — as in Example 4 below,
where $a\,f(n/b) = \tfrac12 f(n)$. It can fail only for contrived oscillating
functions that are periodically tiny one level down; CLRS relegates such $f$ to
the exercises.[^clrs-master] If regularity fails, the theorem does not apply and
you must sum the tree by hand.

**The gaps.** The three cases do not cover every $f$.[^clrs-master] Case 1
needs $f$ _polynomially_ smaller than the watershed (smaller by a factor
$n^\epsilon$), and Case 3 polynomially larger; a merely logarithmic separation
falls into the crack between the cases. The standard example:

$$
T(n) = 2\,T(n/2) + n\log n.
$$

The watershed is $n^{\log_2 2} = n$, and $f(n) = n \log n$ is bigger than $n$
but not bigger by any $n^\epsilon$ — for every $\epsilon > 0$,
$\log n = o(n^\epsilon)$. Case 2 fails since $n\log n \ne \Theta(n)$; Case 3
fails since $n\log n \ne \Omega(n^{1+\epsilon})$. The basic Master Theorem
simply does not apply. The recursion tree still works: level $i$ sums to
$2^i \cdot \tfrac{n}{2^i}\log\tfrac{n}{2^i} = n\,(\log n - i)$, so

$$
T(n) \;=\; \sum_{i=0}^{\log_2 n - 1} n\,(\log_2 n - i)
\;=\; n \cdot \Theta(\log^2 n) \;=\; \Theta(n\log^2 n)
$$

— the sum $\log n + (\log n - 1) + \dots + 1$ is arithmetic, totaling
$\Theta(\log^2 n)$. So the answer picks up a _squared_ log, which none of the
three cases predicts. (CLRS's chapter notes discuss extended versions that
handle $f(n) = n^{\log_b a}\log^k n$; for this course, "fall back to the tree"
is the reliable rule.)

### Worked examples

**Example 1, merge sort.** $T(n) = 2\,T(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
$$
T(n) = \Theta(n \log n),
$$
recovering exactly what the tree and substitution gave.

**Example 2, [binary search](/algorithms/sequences/binary-search-on-the-answer).**
$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
$$
T(n) = \Theta(\log n).
$$

**Example 3, leaf-dominated.** $T(n) = 4\,T(n/2) + n$. Now $a = 4$, $b = 2$, so
$n^{\log_2 4} = n^2$. The combine work $f(n) = n = O(n^{2 - \epsilon})$ (take
$\epsilon = 1$) is polynomially _smaller_ than the watershed, which is Case 1, so
$$
T(n) = \Theta(n^2).
$$
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) = 2\,T(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+\epsilon})$
is polynomially _larger_, a Case 3 candidate. Check regularity:
$a\,f(n/b) = 2\,(n/2)^2 = \tfrac12 n^2 = \tfrac12 f(n) \le k\,f(n)$ with
$k = \tfrac12 < 1$. Regularity holds, so
$$
T(n) = \Theta(n^2).
$$
The root's quadratic work swamps the tree beneath it.

## Unequal splits and Akra–Bazzi

The Master Theorem requires every subproblem to have the _same_ size $n/b$.
Divide-and-conquer algorithms do not always split evenly: a partition step can split $n$
elements into a third and two-thirds, giving

$$
T(n) \;=\; T(n/3) + T(2n/3) + cn.
$$

No single $b$ fits, so the theorem does not apply. The recursion tree still works.
Each node of size $m$ does $cm$ work and splits into children of sizes $m/3$
and $2m/3$ — which together are all of $m$ again. So every level where no
branch has bottomed out sums to exactly $cn$; once leaves start dropping out,
levels sum to _at most_ $cn$.

$$
% caption: Recursion tree for $T(n) = T(n/3) + T(2n/3) + cn$. The two children of a
%          size-$m$ node have sizes summing to $m$, so every full level again sums to
%          $cn$. The shallowest branch (all thirds) dies at depth $\log_3 n$, the deepest
%          (all two-thirds) at depth $\log_{3/2} n$; both are $\Theta(\log n)$, so
%          $T(n) = \Theta(n\log n)$.
\begin{tikzpicture}[
  every node/.style={draw, minimum size=6mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % level 0
  \node (r) at (0,0) {$cn$};
  % level 1: uneven children
  \node (a) at (-2.4,-1.5) {$c\tfrac{n}{3}$};
  \node (b) at (2.4,-1.5) {$c\tfrac{2n}{3}$};
  % level 2
  \node (a1) at (-3.5,-3.0) {$c\tfrac{n}{9}$};
  \node (a2) at (-1.3,-3.0) {$c\tfrac{2n}{9}$};
  \node (b1) at (1.3,-3.0) {$c\tfrac{2n}{9}$};
  \node (b2) at (3.5,-3.0) {$c\tfrac{4n}{9}$};
  \draw (r) -- (a); \draw (r) -- (b);
  \draw (a) -- (a1); \draw (a) -- (a2);
  \draw (b) -- (b1); \draw (b) -- (b2);
  \node[draw=none] at (0,-4.0) {$\vdots$};
  % per-level sums in a right-hand column
  \node[draw=none, black] at (7.2,0.9) {level sum};
  \node[draw=none, text=acc] at (7.2,0) {$cn$};
  \node[draw=none, text=acc] at (7.2,-1.5) {$c\tfrac{n}{3} + c\tfrac{2n}{3} = cn$};
  \node[draw=none, text=acc] at (7.2,-3.0) {$c\tfrac{n}{9} + c\tfrac{2n}{9} + c\tfrac{2n}{9} + c\tfrac{4n}{9} = cn$};
  \node[draw=none, text=acc] at (7.2,-4.0) {at most $cn$};
\end{tikzpicture}
$$

The tree's depth is no longer uniform. The leftmost branch divides by $3$ each
step and reaches size $1$ at depth $\log_3 n$; the rightmost divides by only
$3/2$ and survives until depth $\log_{3/2} n$. Both depths are
$\Theta(\log n)$ — logarithms to different constant bases differ by a constant
factor — so

$$
cn \cdot \log_3 n \;\le\; T(n) \;\le\; cn \cdot \log_{3/2} n
\quad\Longrightarrow\quad T(n) = \Theta(n\log n),
$$

and substitution certifies the guess in the usual way. Erickson works this
recurrence as the standard example of a tree the Master Theorem cannot
handle.[^erickson-recurrences]

For a general tool, the **Akra–Bazzi method** solves the whole family

$$
T(n) \;=\; \sum_{i=1}^{k} a_i\,T(n/b_i) + f(n),
\qquad a_i > 0,\ b_i > 1,
$$

with different-sized subproblems and reasonable $f$. Stated without proof:
find the unique exponent $p$ with $\sum_{i=1}^{k} a_i / b_i^{\,p} = 1$; then

$$
T(n) \;=\; \Theta\!\parens{\,n^p \parens{1 + \int_1^n \frac{f(u)}{u^{p+1}}\,du}}.
$$

For $T(n) = T(n/3) + T(2n/3) + n$ the balance equation is
$\parens{\tfrac13}^p + \parens{\tfrac23}^p = 1$, satisfied by $p = 1$ (a third
plus two-thirds is one). The integral is
$\int_1^n \frac{u}{u^2}\,du = \ln n$, so
$T(n) = \Theta(n\,(1 + \ln n)) = \Theta(n\log n)$, agreeing with the tree. The
method also handles floors, ceilings, and small perturbations of the
subproblem sizes, which is why its answer can be trusted for the real
$T(\floor{n/3})$-style recurrences that code produces. CLRS's chapter notes
present Akra–Bazzi as the standard generalization of the Master
Theorem;[^clrs-akra] at this course's level, the balance-equation-plus-integral
recipe is all you need, with the tree as a cross-check.

## Choosing a method

The methods are complementary, and Erickson in particular urges fluency
with all of them:[^erickson-methods]

- **Recursion tree:** fastest for _building intuition_ and _guessing_ the answer;
  shows where the work concentrates, and handles uneven splits.
- **Master Theorem:** fastest for _getting the answer_ when the recurrence fits
  the $a\,T(n/b) + f(n)$ template; no derivation needed, but it has gaps.
- **Akra–Bazzi:** the heavier tool for unequal subproblem sizes, such as
  $T(n) = T(n/3) + T(2n/3) + n$; solve the balance equation, evaluate one
  integral.
- **Substitution:** the _rigorous_ method that always works and produces a proof;
  use it to certify a guess, or when the others do not apply.

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.

## Recurrences of other shapes

The recurrences here shrink $n$ by a _constant factor_, the divide-and-conquer
signature. **Linear recurrences** with constant coefficients, like
$T(n) = T(n-1) + T(n-2)$ (Fibonacci), instead yield to their characteristic
equation, whose roots give the closed form — Fibonacci's dominant root is the
golden ratio, so $F_n = \Theta(\phi^n)$.[^linear-recurrences] And the Akra–Bazzi
method generalizes to the **Akra–Bazzi–Leighton** form, which admits lower-order
perturbations inside each recursive call, putting the floor/ceiling hand-waving
on rigorous footing.[^akra-bazzi-leighton] For anything that fits none of these,
the recursion tree plus a substitution proof never stops applying.

## 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. The step must land on the _exact_
  bound with the same constant — "$\le cn + n$, which is $O(n)$" is not a proof.
  Strengthen the hypothesis (raise the order, or subtract a lower-order term as
  in $T(n) \le cn - d$) if a residual blocks the step.
- The **combine cost drives the answer.** Counting inversions has the merge-sort
  _shape_ $2\,T(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) = a\,T(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). Behind each case is a
  geometric series of level sums $a^i f(n/b^i)$; for $f(n) = \Theta(n^d)$ the
  ratio $a/b^d$ against $1$ decides the case in one division.
- The cases have **gaps**; when $f$ is only non-polynomially separated from the
  watershed, as in $T(n) = 2T(n/2) + n\log n$ (which sums to $\Theta(n\log^2 n)$),
  fall back to the tree or substitution.
- **Unequal splits** like $T(n) = T(n/3) + T(2n/3) + n$ escape the Master
  Theorem but not the tree: full levels still sum to $cn$ over $\Theta(\log n)$
  depth, giving $\Theta(n\log n)$. **Akra–Bazzi** generalizes: solve
  $\sum a_i/b_i^{\,p} = 1$ for $p$, then integrate $f$.

[^skiena-floors]: **Skiena**, §2.7–2.10 — Logarithms, Recurrences, Divide-and-Conquer: justification for dropping floors and ceilings in recurrences since they perturb the answer by lower-order amounts.
[^clrs-tree]: **CLRS**, Ch. 4 — Divide-and-Conquer: the recursion-tree derivation that merge sort runs in $\Theta(n\log n)$ time.
[^clrs-subst]: **CLRS**, Ch. 4 — Divide-and-Conquer: the substitution method's pitfalls — the "$\le cn + n$, hence $O(n)$" fallacy of not proving the exact inductive form, and the subtract-a-lower-order-term fix for $T(n) = 2T(\floor{n/2}) + 1$.
[^skiena-master]: **Skiena**, §2.10 — Divide-and-Conquer Recurrences: the Master Theorem stated by comparing $f(n) = n^d$ against $n^{\log_b a}$, i.e. the ratio $a/b^d$ against $1$.
[^clrs-master]: **CLRS**, Ch. 4 — Divide-and-Conquer: the Master Theorem for $T(n) = a\,T(n/b) + f(n)$, the recursion-tree proof over the level sums $a^i f(n/b^i)$, the regularity condition, and the gaps where the theorem does not apply.
[^erickson-recurrences]: **Erickson**, _Algorithms_, Ch. 1 and the appendix on solving recurrences: level-by-level analysis of the uneven-split tree $T(n) = T(n/3) + T(2n/3) + n$.
[^clrs-akra]: **CLRS**, Ch. 4 chapter notes — the Akra–Bazzi method for divide-and-conquer recurrences with unequal subproblem sizes: the balance equation $\sum a_i/b_i^{\,p} = 1$ and the integral form of the solution.
[^erickson-methods]: **Erickson**, _Algorithms_, Ch. 1–2 — Recursion; Backtracking & Divide-and-Conquer: the case for fluency with recursion trees, substitution, and the Master Theorem as complementary methods.
[^linear-recurrences]: **CLRS**, Ch. 4 problems and Appendix — linear recurrences and the characteristic-equation method; the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ has closed form $\Theta(\phi^n)$ with $\phi = (1+\sqrt5)/2$.
[^akra-bazzi-leighton]: Leighton, T. (1996). "Notes on better master theorems for divide-and-conquer recurrences." — the Akra–Bazzi–Leighton generalization admitting lower-order perturbations (floors/ceilings) inside each subproblem.