Recipe

Read off a, b, f(n), and evaluate at a size

Use when: an algorithm is described by how it splits its input recursively, and you need its cost recurrence $T(n)=aT(n/b)+f(n)$ , or a specific numeric value of $T$

Goal: the correct recurrence, or a specific value of $T(n)$ computed from it

Taught in Divide-and-conquer algorithms as recurrences · a later section extends this recipe with more cases

Quick recipe

Count the number of recursive calls actually made
Find how much smaller each subproblem is
Identify the non-recursive work $f(n)$
If a specific value of $T$ is requested, unwind from the base case upward

1
Read $a$ as how many subproblems are actually solved recursively, regardless of how many pieces the input was described as being split into.

Example

An algorithm splits its input into $3$ pieces but recurses on only $2$ of them: $a=2$ .

Why: $a$ counts calls that are actually solved recursively, not the number of pieces the input happened to be divided into.
2
Read $b$ as the factor by which the input shrinks for each recursive call.

Example

Each of the $2$ recursive calls gets a third of the input: $b=3$ .

Why: $b$ measures the shrink factor, always sitting in the denominator $n/b$ , never the number of pieces the input was cut into.
3
Everything the algorithm does outside the recursive calls, splitting the input and combining the results, is $f(n)$ .

Example

Combining the $2$ results back together takes time proportional to $n$ : $f(n)=n$ .

Why: $f(n)$ is exactly the work the algorithm would still do even if the recursive calls were somehow free.
4
Starting from the known base case, apply $T(n)=aT(n/b)+f(n)$ repeatedly at increasing sizes until reaching the requested $n$ .

Example

With $a=3$ , $b=3$ , $f(n)=n$ , and $T(1)=1$ : $T(3)=3T(1)+3=6$ , then $T(9)=3T(3)+9=27$ .
- only the recurrence itself is requested — stop after Step 3, no unwinding needed.
- a specific numeric value of $T(n)$ is requested — continue unwinding level by level from the base case up.
Why: unwinding from the smallest known value upward is the only way to get an exact number; the master theorem, next section, gives the growth rate but not this exact value.

Common mistakes

Counting the number of pieces the input is split into instead of the number that are actually recursed on, a subtle but real difference when an algorithm discards some pieces.
Writing $b$ as how many pieces exist rather than how much smaller each recursive call's own input is.
Leaving a genuinely linear combine step out of $f(n)$ , or conversely treating it as constant when it actually scales with $n$ .
Trying to unwind downward from the requested $n$ instead of upward from the base case, which needs the base value already known at the bottom.