"Amortized O(1)" shows up all over this site — Dynamic Array push, Union-Find's find, Fibonacci Heap's decrease-key, Splay Tree's every operation — each time asserted, each
time with a plausibility argument, but never with the actual proof technique laid out on its own.
This page is that technique: three different ways to prove a bound that isn't about any single
operation, verified live against a real push simulator and the exact potential-function argument
Splay Tree's own Complexity section
names and defers.
Every push below either costs 1 (there's room) or 1 + length
(capacity is full — double it and copy everything over first). Two running numbers track two of the
three proof methods below at once: the aggregate line is just total cost divided by
total pushes, and the credit balance is the accounting method's ledger — charge
3 credits per push, spend 1 on the push itself and bank 2,
then pay every resize's real cost out of the bank. Watch the balance dip sharply at every power-of-two
push and recover — and never once go negative, no matter how many resizes stack up.
These sound alike and mean very different things. Average case is a
probabilistic claim: assume some distribution over inputs (random keys, uniform hashing) and ask
what typically happens. It comes with an escape hatch for an adversary — Quicksort's O(n log n) is a genuine average-case
bound, and a specific input (already-sorted data against a last-element pivot) defeats it, landing
on that page's own O(n²) worst case instead. Amortized is a
worst-case claim about a sequence: no matter which operations an adversary picks, in
whatever order, the total cost over any run of n operations is bounded, so the average
per operation is too. Dynamic Array's push has no adversarial input that defeats its O(1)
amortized bound — every one of the three methods below proves that bound holds unconditionally, not
just typically. The demo above charges real reallocation cost on every single push; there's no
"unlucky" sequence to feed it that breaks the credit balance's non-negative invariant, because the
proof doesn't depend on luck.
The simplest of the three: just add up the total cost of any n operations and
divide by n. For doubling growth starting from capacity 1, resizes happen at pushes
1, 2, 4, 8, 16, ... — a resize at push 2^k costs 2^k element-copies, and
those costs form a geometric series that sums to under 2n even before counting the
n individual insert costs. Total cost across any n pushes is under
3n, so the average is a constant — O(1) — regardless of n.
This isn't just algebra: running the demo's own simulator for 1,000 pushes gives a total cost of
2,023 element-touches, for an aggregate amortized cost of 2.023
per push — a real number landing exactly where the geometric-series bound says it must, not merely
under it.
The aggregate method is easy to apply but coarse: it proves a bound on the average over the whole sequence and nothing more granular than that. It can't say anything about how the cost is distributed across individual operations, which is exactly what the next two methods add.
Assign each operation an amortized cost you get to choose, as long as the running total
of amortized costs charged never falls below the running total of real costs incurred — equivalently,
track the running surplus (amortized paid minus real cost) as a credit balance and require it never
goes negative. For push: charge 3 credits. Spend 1 immediately on
inserting the new element; bank the other 2. When a resize copies k
elements, pay that real cost of k out of the bank rather than charging the push
anything extra. The classic argument for why this never overdraws: a resize from capacity
k to 2k only happens after exactly k pushes have occurred
since the previous resize (from k/2 to k), and each of those
k pushes banked 2 credits — 2k banked against a
k-element copy, twice what's needed. The demo above runs this exact ledger: over
1,000 pushes the balance's lowest point ever reached is 2 credits, confirmed by
simulation, not just argued — it dips at every resize and always recovers before the next one, the
concrete shape of "never negative" playing out.
The payoff over the aggregate method: this proof is local. Each operation's amortized cost is fixed and known the moment it happens — 3 credits, always — which is exactly what makes it provable that the sequence-wide bound holds no matter where you stop or how the operations are interleaved with anything else. The aggregate method only ever answers "what's the total," after the fact.
The most general of the three, and the one Splay Tree's own Complexity section names
("proven with a potential-function argument this page doesn't reproduce") without showing. Define a
potential function Φ over the data structure's whole state — some single number that
summarizes how much "stored-up debt" the structure is carrying — such that Φ starts at
its minimum and never goes below it. Then for any operation, define:
amortized cost = actual cost + Φ(after) − Φ(before)
If this amortized cost is bounded for every operation, the real total cost of any sequence is
bounded too — because the ΔΦ terms telescope: summed over a whole sequence, every
"after" cancels the next operation's "before," leaving only Φ(final) − Φ(initial),
which is bounded since Φ never dips below its floor. An operation that does a lot of
real work but drives Φ down by even more has an amortized cost that's small or even
negative — it's cashing in potential banked by earlier, cheaper operations instead of spending new
credit, the same idea the accounting method's ledger tracks, generalized to any numeric summary of
state instead of only per-element credits.
Splay Tree's own argument, reproduced. Define Φ = Σ log₂(size(v)),
summed over every node v in the tree, where size(v) is the number of
nodes in v's subtree. The access lemma — the result Splay Tree's page
defers — states that splaying node x up to the root costs at most
3(log₂(size(root)) − log₂(size(x))) + 1 amortized, where both sizes are measured
before splaying. Checked against that page's own loaded demo, not a fresh example: inserting
1 through 7 ascending builds a 7-node right-leaning chain, and searching for 4 (the page's own
suggested action, which it says collapses the chain from height 7 to height 4) splays a node at
depth 3 whose own subtree held nodes 4 through 7 — size(x) = 4, size(root) =
7. Simulating the real zig-zig-then-zig rotation sequence: 3 rotations plus
the initial visit gives an actual cost of 4; the potential drops from
Φ = 12.299 before (a lopsided 7-node chain, mostly large subtrees) to Φ = 7.977
after (two balanced 3-node arms under the new root, mostly small subtrees) — a drop of
4.322. Amortized cost is 4 + (7.977 − 12.299) = −0.322, comfortably
under the access lemma's own bound of 3(log₂7 − log₂4) + 1 = 3.422 for this case — and
negative, meaning this particular splay banked more potential than it spent, exactly the kind of
operation that pays forward for a future expensive one. Why the potential function is shaped this
way: subtrees near the root are large, so nodes near the root contribute a lot to Φ;
moving a deep node (small subtree, near the bottom) up to the root shrinks a chain of large
subtrees into two smaller balanced ones, and it's exactly the nodes on the access path — the ones
the real rotations touch — whose subtree sizes change. The full case-by-case proof (separately
bounding zig, zig-zig, and zig-zag) is standard and not reproduced move-by-move here, but the
function itself and one concrete, verified instance of it now are — the part this page's own
Complexity section leaves as a name only.
O(1) amortized via a geometric-series argument either way.O(log n) amortized, but any single one can be
O(n) — the one entry on this site whose amortized bound offers zero per-operation
guarantee at all.O(log n), and path compression only ever
shortens paths, never lengthens them, so there's no way to "bank" cost against future operations
the way splaying deliberately does — the combination lands on O(α(n)) amortized
without the page needing to name the technique.extractMin call pays it all down at once. That page measures
the spike directly — 7, 95, 991, and 9,991 root-merges after 10, 100, 1,000, and 10,000 plain
inserts — the real-numbers version of the same telescoping-sum idea proven with a formula above.Treating "amortized O(1)" as "every call is fast." The whole point of the
technique is that some calls aren't — a
single extractMin after 10,000 lazy inserts performs 9,991 root-merges, and a single search on this page's own loaded chain
walks all 7 nodes before any rebalancing even starts. A system with a hard per-call latency
budget — a real-time deadline, a UI thread that can't stutter — can't rely on an amortized bound no
matter how good it looks on paper; it needs a genuine worst-case-per-operation guarantee instead,
which is exactly the trade AVL and red-black trees make against Splay Tree's better
amortized bound.
Assuming an amortized bound is a probabilistic one. It isn't, and the
distinction has teeth: an amortized bound holds for every sequence an adversary can construct,
while an average-case bound (Quicksort's O(n log n)) explicitly does not — see above. Reaching for "it's probably fine on average" to justify skipping a
real amortized proof is reasoning about the wrong kind of claim entirely.
Resetting the structure and assuming the slate is clean. The accounting method's
credit balance and the potential method's Φ are properties of the current state,
not of history — a freshly built structure starts at whatever Φ or balance its initial
state implies, not zero by default unless the state itself is empty. Clearing Dynamic Array back to its initial capacity (as its
own Clear button does) genuinely does reset both to their starting values, but a
structure that keeps some nodes around after a bulk operation carries whatever potential those nodes
still represent — the bound applies to the state as it actually is, not to what an operation was
originally intended to leave behind.