Foundations — Master theorem — solving recurrences T(n) = aT(n - b) + f(n)

Before you can trust the formula, you must be able to point at a picture for every letter in $T(n)=aT(n/b)+f(n)$. This page builds each one from nothing, in the order they depend on each other.

0. What is $n$? (the size of the problem)

Picture a row of $n$ boxes. If you have 8 numbers to sort, $n=8$. Everything in this topic asks: as $n$ grows huge, how does the running time grow? We never care about small $n$; we care about the trend.

1. What is $T(n)$? (the running-time function)

The word recurrence below just means: $T$ defined in terms of smaller copies of itself. That is the shape of every divide-and-conquer cost.

2. The recurrence $T(n)=aT(n/b)+f(n)$ — reading it left to right

This one line is the entire topic. Read it as a sentence:

"The time to solve size $n$ equals ( $a$ copies of the time to solve a shrunken problem of size $n/b$ ) plus the extra work $f(n)$ I do myself at this level."

Three new symbols live here. We define each with its picture.

2a. $a$ — how many subproblems you make

Picture one box that splits into $a$ arrows pointing down to $a$ smaller boxes.

2b. $b$ — how fast the problem shrinks

2c. $f(n)$ — the work you do yourself at this level

3. Powers and $b^i$ — counting down the tree

To read the tree we need $b^i$ ("$b$ multiplied by itself $i$ times").

Why do we need it? Because at level $i$ of the recursion tree, each subproblem has size $\frac{n}{b^i}$ and there are $a^i$ of them. Powers are simply the bookkeeping for "how deep are we, and how many boxes are there."

4. Logarithms — the height of the tree

Here is the tool that scares people. We introduce it because we must answer one specific question: how many times can I divide $n$ by $b$ before I hit size 1?

The stopping condition of the tree: size $\frac{n}{b^L}=1\Rightarrow b^L=n\Rightarrow L={\log }_{b}n$. That $L$ is the height — the number of floors in the building.

5. The two log identities you'll actually use

Plain-words proof of the swap: write $a=b^{{\log }_{b}a}$, so $a^{{\log }_{b}n}={\left(b^{{\log }_{b}a}\right)}^{{\log }_{b}n}=b^{{\log }_{b}a\cdot {\log }_{b}n}={\left(b^{{\log }_{b}n}\right)}^{{\log }_{b}a}=n^{{\log }_{b}a}.$ We just reshuffled the exponents (multiplication of exponents commutes) and used $b^{{\log }_{b}n}=n$.

6. $c_{\text{crit}}={\log }_{b}a$ — the critical exponent

Picture: the bottom row of the tree has $n^{{\log }_{b}a}$ tiny boxes. That is the "pile of chores at the bottom." The entire Master Theorem is one comparison — race $f(n)$ against $n^{{\log }_{b}a}$.

• $a$ big (many branches) → more leaves → $c_{\text{crit}}$ big → leaf pile heavy.
• $b$ big (fast shrink) → shorter tree → fewer leaves → $c_{\text{crit}}$ smaller.

7. Asymptotic symbols $O,\Omega ,\Theta$ — the comparison ruler

The three cases say "$f$ is smaller", "equal", "bigger". Those words need a precise meaning that ignores constants and only cares about the growth trend.

8. Geometric series — why there are exactly three cases

See Geometric Series. When we add up the work across all levels of the tree, level-$i$ cost divided by level-$(i-1)$ cost is a constant ratio $r$. Those three behaviours of $r$ are exactly Case 1, Case 2, Case 3 — leaves win, tie (multiply by height), root wins. The three cases are not arbitrary; they are the three moods of a geometric series.

Prerequisite map

Equipment checklist