Intuition The ONE core ideaSome operations are rarely expensive but usually cheap, so judging each by its worst single case tells a lie about the true total work. Amortized analysis measures the guaranteed average cost across a whole sequence — like paying a small flat fee every time so the occasional huge bill is already covered.
Before you can read a single line of the parent topic , you must own every symbol it throws at you. This page builds each one from nothing, in the order they depend on each other.
Definition Operation, sequence, andm operation is one single action you ask a data structure to do — a push, an increment, a union. A sequence is a list of these actions done one after another. The letter == m == count of operations in that sequence.
Picture a row of m i i left → right ; nothing is random, nothing is reordered.
Figure s01 — A row of m c i = 1
Why the topic needs this: amortized analysis is a claim about a whole row of boxes , not about one box. Every symbol below is a way of talking about that row.
c i i c i c i actual amount of work operation number i push touch?". The little i index : which box in the row we mean.
Picture: above each box, write the true number of steps it took. Most are tiny (c i = 1 c i = 4 c i = 8
Intuition Why we can't just use the biggestc i 100 1 every box "100 100 × on average without pretending the spikes vanish.
∑ ∑ i = 1 m c i add up c i i 1 m ∑ i = 1 m c i = c 1 + c 2 + c 3 + ⋯ + c m . ∑ i = 1 start counting ; the number on top (here m stop .
T ( m ) T ( m ) = ∑ i = 1 m c i grand total of real work across the whole sequence. It is a single number: the height of all the bars added together.
Why the topic needs it: the honest average is T ( m ) / m T ( m ) without summing every spike by brute force.
c ^ i hat in c ^ i c i we invent — the price we charge for operation i c i ∑ i = 1 m c ^ i ≥ ∑ i = 1 m c i . never undercount the total real work.
c ^ c ^ without an index is the one number we advertise as "the amortized cost per operation". It is the average of our charges:
c ^ = m 1 ∑ i = 1 m c ^ i . c ^ i one box; c ^ all boxes.
Intuition Why we are allowed to report a single averagec ^ ∑ c ^ i ≥ ∑ c i = T ( m ) m c ^ ≥ T ( m ) / m c ^ never understates the real per-operation cost — it is a guaranteed ceiling. Reporting one flat price is legitimate only because it sits above the honest average, not because the spikes disappeared.
Intuition Picture: flat pricingImagine a market stall charging a flat $3 for every item even though some items cost the seller $1 and one rare item costs $100. As long as the flat prices collected add up to at least what the seller actually spent, the stall never loses money. c ^ ≥
Definition Big-O in one breathO ( 1 ) bounded by a constant no matter how big the structure grows" — flat. O ( n ) in proportion to the number of elements n n Big-O, Big-Omega, Big-Theta for the full family.
Picture two curves: O ( 1 ) O ( n ) O ( n ) O ( 1 ) on average .
Figure s02 — Two cost curves against structure size n O ( n ) O ( 1 )
D i D i state of the data structure after operation i D 0 D i i i + 1
n s dynamic array : == n == currently stored ; == s == capacity , i.e. how many slots are allocated. Always n ≤ s n s
Picture a shelf with s n
Figure s03 — A shelf of s n
Definition A geometric seriesA geometric series is a sum where each term is a fixed multiple of the last. The one that matters here doubles:
1 + 2 + 4 + 8 + ⋯ + 2 k = 2 k + 1 − 1. sum is less than twice the last term . See Geometric Series .
Intuition The picture that makes doubling "free-ish"Stack blocks of width 1 , 2 , 4 , 8 , … everything before it combined, plus one . So the whole stack is barely wider than the final block. Copies during table doubling cost 1 + 2 + ⋯ + 2 k < 2 m
Figure s04 — Doubling blocks of width 1 , 2 , 4 , 8 = 15 = 8 2 m
Why the topic needs it: this single inequality is why the aggregate method gives T ( m ) < 3 m O ( 1 )
Φ Φ ( D i ) number we attach to a state D i Φ ( D 0 ) = 0 Φ ≥ 0
ΔΦ Δ change in ". So
Δ Φ i = Φ ( D i ) − Φ ( D i − 1 ) up or down during operation i c ^ i = c i + Δ Φ i plus whatever you added to (or took from) savings.
≥ 0 Φ ( D 0 ) = 0 c ^ i telescope — every Φ ( D i ) ∑ c ^ i = ∑ c i + Φ ( D m ) − Φ ( D 0 ) Φ ( D 0 ) = 0 Φ ( D m ) ≥ 0 ≥ 0 ∑ c ^ i ≥ ∑ c i
The parent topic solves everything three different ways. You do not need the details yet — just recognise the names when the map below uses them:
Definition The three accounting methods, in one line each
Aggregate method — "just add it all up": compute the total T ( m ) c ^ = T ( m ) / m Accounting (banker's) method — "prepay and bank credit": over-charge cheap operations, store the surplus as credit on elements, and let expensive operations spend that saved credit instead of charging the user.Potential method — "stored energy": track a single number Φ c ^ i = c i + Δ Φ i Φ
These same symbols power the harder examples the parent links: credits-on-bits for the Disjoint Set Union (Union-Find) and rank arguments, potential for Splay Trees and Fibonacci Heaps . Master them here once.
The diagram below shows how the foundations feed into the three methods and finally into the topic.
operation and sequence, m
summation and total T of m
accounting method credits
potential Phi and delta Phi
Recall Plaintext walkthrough of the map (read this if the diagram does not render)Start at "operation and sequence, m c i T ( m ) c ^ c ^ aggregate (also fed by "dynamic array n , s accounting (credits), and potential (fed by "Φ ΔΦ Amortized analysis — the parent topic. In short: symbols → c ^
Test yourself — each line is a question ::: answer reveal.
What does the index i c i Which operation in the sequence we mean — the i
Read ∑ i = 1 m c i Add up the actual cost of every operation from the first (i = 1 i = m
What is T ( m ) The total actual cost of the whole sequence, ∑ i = 1 m c i
What does the hat in c ^ i A cost we choose to charge for one operation, which may differ from the real c i ∑ c ^ i ≥ ∑ c i
Difference between c ^ i c ^ c ^ i c ^ = m 1 ∑ c ^ i
Why may we report the single average c ^ Because ∑ c ^ i ≥ T ( m ) m c ^ ≥ T ( m ) / m
O ( 1 ) O ( n ) O ( 1 ) O ( n )
For a dynamic array, what are n s n s n ≤ s n = s
Value of 1 + 2 + 4 + ⋯ + 2 k 2 k + 1 − 1 < 2 m
What is Φ ( D i ) Stored energy of state D i Φ ( D 0 ) = 0 Φ ( D i ) ≥ 0 i
What does Δ Φ i Φ ( D i ) − Φ ( D i − 1 ) i
State the master equation of the potential method. c ^ i = c i + Φ ( D i ) − Φ ( D i − 1 )
Name the three methods in one word each. Aggregate (add-and-divide), Accounting (bank credit), Potential (stored energy Φ
