1
A recursion tree is the master theorem's proof, drawn
Sum the work at each level and add up the levels. It applies to uneven splits, where the theorem does not.
Lesson · Algorithms and Complexity · Analysis
Recursion Trees and Amortised Analysis
A recursion tree solves recurrences the master theorem cannot. Amortised analysis answers a different question: what a sequence of operations costs on average, when one of them is occasionally expensive.
recursion tree: sum the work level by level
amortised cost = total cost of a sequence / number of operations
a doubling array: worst case Θ(n) per insert, amortised Θ(1)
amortised is a GUARANTEE, not an average over random inputs
Two techniques
Core ideas
What this lesson establishes
One technique for recurrences the theorem misses, and one for the case where the worst case is a bad summary.
2
Amortised analysis bounds a sequence
Not a single operation. Occasional expensive operations are paid for by many cheap ones.
3
Amortised is not average-case
It is a worst-case guarantee over any sequence, with no probability. Averaging over random inputs is a different claim.
The material
Two techniques
Recursion trees for awkward recurrences, amortisation for uneven costs.
Recursion trees
Draw the recursion as a tree: the root does the top-level combining work, its children are the subproblems, and so on to the base cases. The total cost is the sum of the work at every node, which is best computed level by level.
Example · An uneven split
T(n) = T(n/3) + T(2n/3) + n. Each level does n units of combining work, because the subproblem sizes at each level still sum to n. The deepest branch shrinks by 2/3 each time, so the depth is log_{3/2} n. Total: Θ(n log n) — the same as an even split.
That is why quicksort survives an imperfect pivot. Any constant-fraction split gives logarithmic depth, and only a consistently extreme pivot — splitting off one element at a time — produces the quadratic worst case.
Example · A tree with unequal levels
T(n) = 2T(n/2) + n². Level i has 2ⁱ subproblems of size n/2ⁱ, doing 2ⁱ(n/2ⁱ)² = n²/2ⁱ work. The total is n² Σ 1/2ⁱ < 2n², so T(n) = Θ(n²): the root dominates, and the master theorem agrees since log₂2 = 1 < 2 = d.
Amortised analysis
Definition · Amortised cost
The amortised cost of an operation is the total cost of a worst-case sequence of m operations, divided by m. It is a guarantee about sequences, not about any single operation.
Theorem · The doubling array
A dynamic array that doubles its capacity when full, copying all elements, supports insertion in Θ(1) amortised time, even though a single insertion can cost Θ(n).
Consider n insertions starting from capacity 1. The copies happen when the size reaches 1, 2, 4, 8, …, costing 1 + 2 + 4 + ⋯ + 2^{⌊log₂ n⌋} < 2n element moves in total.
Adding the n insertions themselves, the total is under 3n, so the amortised cost per insertion is under 3 — a constant.
□
The geometric series is doing the work: the expensive operations are rare and their cost grows exactly as fast as the gaps between them, so the total telescopes. The geometric sum of “Induction with Sums and Products”, in Induction and Recursion, is the calculation.
Doubling is essential. Growing by a fixed amount c instead means copies at sizes c, 2c, 3c, …, totalling Θ(n²) moves — an amortised cost of Θ(n) per insertion. The two policies differ by a whole class.
The three methods
AGGREGATE total cost of m operations, divided by m
ACCOUNTING charge each cheap operation extra; save the credit
to pay for the rare expensive one
POTENTIAL define a potential function Φ on the data structure;
amortised cost = actual cost + ΔΦ
The accounting method applied to the doubling array: charge 3 units per insertion — one to insert, one saved to copy this element later, one saved to copy an older element. When the array doubles, every element has exactly the credit needed for its move.
Amortised is not average-case. Average-case analysis assumes a distribution over inputs and computes an expectation. Amortised analysis assumes nothing and bounds the total for any sequence, which is a strictly stronger guarantee.
Interactive
Algorithms and growth
Counts from running, not from quoting
Method
Using each technique
Tree for a recurrence, amortisation for a sequence.
1
Draw the tree when the master theorem does not apply
Uneven splits, varying subproblem sizes, or a forcing term between the cases.
2
Sum the work level by level
Then sum over levels. The depth is set by the branch that shrinks slowest.
3
For amortisation, bound the total over a sequence
Not the worst single operation. A geometric series usually appears.
4
Say which guarantee you have
Amortised bounds hold for any sequence; average-case bounds need a distribution. They are different claims.
Trees and amortisation
Score 0 / 0Choose the answer you can justify.
The doubling array, counted
Inserting 16 elements, starting from capacity 1.
insert 1 capacity 1→1 copies 0
insert 2 capacity 1→2 copies 1
insert 3 capacity 2→4 copies 2
insert 5 capacity 4→8 copies 4
insert 9 capacity 8→16 copies 8
inserts 10–16 copies 0
total copies = 1 + 2 + 4 + 8 = 15 < 16 = n
total cost = 16 inserts + 15 copies = 31 < 2n
amortised cost per insertion < 2
worst single insertion = 9 (the resize at element 9)
GROWING BY 1 INSTEAD: copies = 1+2+…+15 = 120 = Θ(n²)
amortised cost per insertion = Θ(n)
The last two lines are the point. Doubling and incrementing look like minor implementation choices and differ by a whole complexity class. Every dynamic array in every standard library doubles for this reason.
The "< 2n" above is a fact about n = 16, a power of two, where the last doubling is well past. One insert later, at n = 17, the array doubles again: 31 copies, total 48, amortised 2.82 — above 2 and still below the 3 the proof guarantees for every n. That is why the theorem is stated with 3.
Common mistakes
1
Confusing amortised with average-caseAmortised holds for every sequence with no probabilistic assumption. It is the stronger guarantee.
2
Summing a recursion tree by branch instead of by levelLevel by level is what makes the sums tractable, because the sizes at each level usually add to something simple.
3
Assuming any growth policy gives amortised constant timeOnly geometric growth does. Fixed increments give Θ(n) amortised.
Check your understanding
✓
Finish when you can produce the geometric series yourself.
Show that a dynamic array growing by a factor of 1.5 still has amortised Θ(1) insertion, and identify the ratio of the series. Any constant factor above 1 works, and that is the theorem.
Note: Amortised analysis was named by Tarjan and is what makes union–find, Fibonacci heaps and dynamic arrays practical. In each case a single operation can be slow and no sequence can be, which is the guarantee that actually matters.