Master theorem — solving recurrences T(n) = aT(n - b) + f(n): Visual walkthrough

Step 0 — Reading the equation out loud (nothing assumed)

Definition Every symbol, in plain words

$cost for size n T (n) = how many copies a \cdot cost for a slightly smaller input T (n - b) + extra work at this level f (n)$

$T$ is a machine: feed it a size $n$ , it tells you the total number of steps.
$a \geq 1$ is a whole number: how many smaller copies of the problem you spawn.
$b$ is a positive integer ( $b \geq 1$ ): how much you chop off the size each time, $n \to n - b$ . Keeping $b$ an integer means the sizes $n, n - b, n - 2 b, \dots$ are honest whole numbers and no rounding is needed.
$f (n) > 0$ is the "glue" work — splitting and combining — done right here, before you recurse. For the clean theorem we assume $f$ is polynomially bounded, i.e. $f (n) = Θ (n^{d})$ for some fixed power $d \geq 0$ . (We flag below what happens when $f$ is not polynomial.)
Base case: the recursion stops at some small size $n \leq n_{0}$ , where $T (n_{0}) = Θ (1)$ — solving a constant-size problem costs a constant. We need this stated because the leaf row's cost is (number of leaves) $\times T (base) = (leaves) \times Θ (1)$ .

Contrast anchor: in the divide form the size is halved ( $n \to n /2$ ). Here it is decremented ( $n \to n - 1$ , say). Halving reaches $1$ in about $lo g n$ steps; decrementing by $1$ takes a full $n$ steps. That single fact is the whole story of this page.

We will use the running example $T (n) = 2 T (n - 1) + 1$ throughout, so you can watch the abstract tree fill in with real numbers.

Step 1 — Draw the recursion tree and count its DEPTH

WHAT. We expand $T (n)$ once: it becomes $a$ boxes of $T (n - b)$ plus one box of glue $f (n)$ . Then we expand each of those, and so on, until the size hits the base.

WHY. The total cost is just the sum of glue-work $f$ over every box in the tree plus the cost of the bottom row. To add them we must first know how tall the tree is and how wide each row is. Height comes first because it decides how many rows we sum.

WHAT IT LOOKS LIKE. Look at the figure: the size label drops by $b$ at every level — $n, n - b, n - 2 b, \dots$ — a straight staircase, not a plunge. It reaches the base size (a constant $n_{0}$ ) after $L = \frac{n}{b} levels (the staircase has n / b steps).$

Step 2 — Count the NODES on each level (the width explodes)

WHAT. Each box spawns $a$ children. So one root box becomes $a$ boxes, then $a \cdot a = a^{2}$ , then $a^{3} \dots$

WHY. The bottom-row cost = (number of leaves) $\times$ (cost of one leaf). If $a > 1$ , the number of boxes multiplies every level, and after $L = n / b$ levels this is an astronomically large number. We need its exact size to know whether the leaves dominate.

WHAT IT LOOKS LIKE. In the figure the row widths are $1, a, a^{2}, \dots$ — a widening funnel. The red bottom row is by far the widest.

Step 3 — The two rival costs (the race)

WHAT. As before, two costs fight: the leaf cost (bottom row, $= leaves \times T (base)$ ) versus the root-glue cost ( $f (n)$ at the top).

WHY. We compare them to see who dominates the sum. But here the shapes of the two contestants are wildly different, so the comparison rule is not the same as the divide theorem.

WHAT IT LOOKS LIKE. Two curves in the figure: leaf cost $a^{n / b}$ (a steep exponential, when $a > 1$ ) versus $f (n)$ (a polynomial, e.g. $n$ , $n^{2}$ ). Since we assumed $f$ is polynomial (Step 0), the exponential eventually crushes it — so if $a > 1$ the leaves always win. If $a = 1$ , there is exactly one box per level and the race becomes a simple sum.

Step 4 — Case $a > 1$ : the leaves win (exponential blow-up)

WHAT. With $a > 1$ and polynomial $f$ , we claim $T (n) = Θ (a^{n / b})$ — the leaf row, full stop, with no extra $f (n)$ factor.

WHY. Sum the glue over all levels and add the leaf row: $T (n) = \sum_{i = 0}^{L - 1} a^{i} f (n - ib) + leaf row = a^{n / b} \cdot Θ (1) a^{L} T (base) .$ Each summand $a^{i} f (n - ib)$ is (nodes on level $i$ ) $\times$ (glue per node). Because $a^{i}$ grows exponentially while the polynomial $f (n - ib) \leq f (n)$ can only shrink, the summands increase toward the bottom — a growing Geometric Series, which is dominated by its last summand. That last summand and the leaf row are both $Θ (a^{n / b})$ . So the whole sum is $Θ (a^{n / b})$ : the polynomial $f$ contributes only lower-order terms and does not multiply the answer.

WHAT IT LOOKS LIKE. In the figure the bar heights $a^{i} f (n - ib)$ climb steeply toward the bottom; the tallest bar (the leaves) is essentially the whole area.

Step 5 — Case $a = 1$ : no fan-out, just add up the chain

WHAT. With $a = 1$ every box has exactly one child. The tree is a single vertical chain of $L = n / b$ boxes. So $T (n) = \sum_{i = 0}^{n / b} f (n - ib) + T (base), T (base) = Θ (1) .$

WHY. There is no multiplication of nodes ( $1^{i} = 1$ per level), so the total is a plain sum of the glue values as the size steps down $n, n - b, n - 2 b, \dots$ , plus one constant base cost. There is no "leaves vs root" race — there is only the sum. Its size depends entirely on the shape of $f$ .

WHAT IT LOOKS LIKE. The figure is a single column of boxes; the glue values are like the heights of a staircase, and we are measuring the area under that staircase.

Step 6 — The full case table (cover every input)

The one-picture summary

This final figure stacks the two worlds side by side: on the left, the $a = 1$ chain whose cost is the shaded triangle $Θ (n^{d + 1})$ ; on the right, the $a > 1$ funnel whose cost is the exploding red leaf-row $Θ (a^{n / b})$ . The single decision — does the tree fan out? — routes you to one side or the other.

Recall Feynman: tell it to a 12-year-old (click to reveal)

You have a chore for a pile of size $n$ . Each round you shave off a fixed slice $b$ (say one item), do a little tidy-up $f$ , and hand out $a$ copies of the slightly-smaller chore to friends. When a chore is tiny enough it's done in one fixed instant (that's the base case, a constant).

If each round makes exactly one new chore ( $a = 1$ ), it's just one long line: chore of size $n$ , then $n - 1$ , then $n - 2$ , all the way down. You add up the tidy-up work on each of the $\sim n$ steps. If each tidy-up costs about $n^{d}$ , the total is roughly a triangle: $n$ steps times up to $n^{d}$ each $= n^{d + 1}$ .

If each round makes $a > 1$ new chores, the pile of chores doubles (or triples) every round, and there are hundreds of rounds because you only shave off one item at a time. The number of tiny chores at the bottom is $a$ multiplied by itself $n / b$ times — a colossal exponential $a^{n / b}$ . Each of those tiny bottom chores costs only a fixed instant, but there are so many that they bury everything else — so the total is that count $a^{n / b}$ , with no leftover tidy-up factor. That's exactly why calling fib(n) the naive recursive way is painfully slow: it forks in two every step and never divides the work.

The one question that decides your fate: does the chore fork ( $a > 1$ ) or just march down a line ( $a = 1$ )? Fork → exponential. Line → sum a polynomial.

Connections

Recursion Trees — every figure on this page is a recursion tree; this is the visual engine.
Geometric Series — Step 4's "last term dominates" is the growing-geometric-series fact.
Big-O, Big-Omega, Big-Theta — the $Θ$ comparison machinery used throughout.
Akra–Bazzi method — the general tool when subproblem sizes are mixed or non-constant.
Merge Sort, Karatsuba Multiplication, Binary Search — the divide cousins (parent note); contrast their $lo g n$ depth with this page's $Θ (n)$ depth.
Return to the parent topic.

Flashcards

T (n) = a T (n - b) + f (n)

, how deep is the recursion tree?

L = n / b = Θ (n)

levels — size drops by

b

each level, a linear staircase (not

lo g n

How many leaves does a subtractive tree have when

a > 1

a^{L} = a^{n / b} = (a^{1/ b})^{n}

— exponential in

n

What is the leaf-row cost, and does

f (n)

multiply the answer in Case

a > 1

Leaf row

= a^{n / b} \cdot T (base) = Θ (a^{n / b})

; no,

f

is lower-order (leaves cost

f (const) = Θ (1)

, not

f (n)

Solve

T (n) = 2 T (n - 1) + 1

a = 2 > 1 \Rightarrow Θ (2^{n})

(full binary tree of depth

n

Solve

T (n) = T (n - 1) + n

a = 1

f = n^{1}

d = 1 \Rightarrow Θ (n^{d + 1}) = Θ (n^{2})

When

a = 1

and

f (n) = Θ (n^{d})

, what is

T (n)

Θ (n^{d + 1})

— sum a polynomial down the chain of length

Θ (n)

(triangle area).

What two assumptions make the clean subtractive theorem hold?

Base cost

T (base) = Θ (1)

and

f

polynomial (

f = Θ (n^{d})

); if

f

outgrows the leaves, instead

T = Θ (f (n))

Why can't you use

lo g_{b} a

for the subtract form?

There is no ratio

n / b

, only a difference

n - b

;

lo g_{b} a

is meaningless and gives wrong (polynomial) answers for exponential recurrences.

What single question decides the subtractive case?

Does the tree fan out?

a > 1 \Rightarrow Θ (a^{n / b})

exponential;

a = 1 \Rightarrow Θ (n^{d + 1})

polynomial.