Amortized Analysis

Amortized analysis bounds the total cost of a sequence of operations, then assigns that cost across the operations in the sequence. A single operation may remain expensive. The guarantee is that expensive cases cannot occur often enough to make every operation pay that price.

No probability distribution is required. If every sequence of m operations costs at most O(m·f(n)), the amortized cost is O(f(n)) per operation. This is a deterministic sequence guarantee, unlike the expected bounds discussed in Big-O notation.

The aggregate method derives a bound for the complete sequence and divides by the number of operations. Consider a stack supporting push, pop, and multipop(k), which removes up to k items.

One multipop can take Θ(n) time, but each item can be popped only after it has been pushed. Across m operations starting from an empty stack, at most m pushes and m pops occur. The total is O(m), so each operation costs O(1) amortized.

Incrementing a binary counter may flip many bits. Moving from 0111…1 to 1000…0 flips every trailing one plus one zero, so one increment can cost Θ(log n) for an n-increment sequence.

The least significant bit flips on every increment, the next on every second increment, and bit i once per 2ⁱ increments. The total number of flips is bounded by n + n/2 + n/4 + … < 2n. Increment is therefore O(1) amortized.

A dynamic array allocates a larger block when its capacity is exhausted and copies the existing elements. If capacity grows by a fixed factor greater than one, a resize after n insertions copies O(n) elements in that operation.

Previous copies form a geometric series. With capacity doubling, the total copied before reaching size n is less than 1 + 2 + 4 + … + n < 2n. Appending is O(1) amortized while one append remains O(n) worst-case. A deque implemented with a growable circular array uses the same argument.

The accounting method assigns an artificial charge to each operation. Cheap operations can be charged more than their immediate cost; the surplus is stored as credit and later pays for expensive operations.

For a doubling array, charge each append enough to write the new element and reserve credit for a future copy. The proof must never spend credit that has not been collected. If the balance stays non-negative, the sum of amortized charges is an upper bound on the actual total cost.

The potential method stores prepaid work as a function Φ(D) of the data structure state. For operation i, define amortized cost âᵢ = cᵢ + Φ(Dᵢ) − Φ(Dᵢ₋₁), where cᵢ is the actual cost.

Summing causes the intermediate potential terms to cancel: Σâᵢ = Σcᵢ + Φ(Dₘ) − Φ(D₀). If Φ(D₀) = 0 and potential is always non-negative, total amortized cost upper-bounds total actual cost.

A useful potential measures work that the current state can force later. For a dynamic table, potential can reflect how close the array is to its next resize. For a binary counter, it can be the number of one bits, because those bits are the ones a later increment may clear.

The function is part of the proof, not part of the implementation. It must make expensive operations release enough potential to offset their actual cost while keeping cheap operations' amortized costs bounded.

An amortized bound does not cap individual latency. A dynamic-array append can still trigger a linear copy, and a scapegoat tree update can still rebuild a linear-size subtree. The bound limits how frequently those events can occur.

This distinction matters for real-time and tail-latency requirements. A system may have acceptable total throughput under an amortized bound while violating a deadline during one operation. Worst-case analysis or deamortization is required when every operation needs a cap.

Union-find combines union by rank or size with path compression. A single find may traverse several parent links, then rewrites those links so later queries reach the root more directly.

Tarjan's sequence analysis gives O(m α(n)) time for a standard sequence of m operations on n elements, where α is the inverse Ackermann function. The near-constant result is amortized across the sequence; it is not a constant worst-case bound for each call.

A splay tree rotates every accessed node to the root. One access can take linear time in the current tree, but the access lemma bounds the total restructuring over a sequence and yields O(log n) amortized operations.

Unlike an AVL tree, the splay tree stores no balance metadata and provides no logarithmic worst-case height. Its guarantee depends on the sequence analysis; frequently accessed keys can also move closer to the root.

Storage structures also defer work. An LSM tree buffers writes and later compacts sorted files. The immediate write path avoids an in-place random update, while background compaction performs additional reads and writes.

Amortized reasoning can distribute that maintenance across the writes that caused it, but the resulting cost depends on the compaction policy, size ratio, and level count. A generic “amortized constant” claim is not justified without those parameters.

Deamortization converts occasional large work into smaller scheduled pieces. A table can migrate a bounded number of entries to a new allocation during each ordinary operation instead of copying the complete table at once.

The total amount of work may remain in the same asymptotic class, but its latency distribution changes. Deamortization usually requires additional state, temporary duplication, and rules ensuring that queries consult both old and new representations during migration.

Amortized analysis bounds operation sequences rather than isolated worst cases. Aggregate analysis counts the whole sequence, accounting stores credits on operations or objects, and the potential method represents prepaid work as a state function.

The result is deterministic and does not imply that every operation is cheap. Use it for throughput guarantees when expensive events are necessarily sparse; use worst-case bounds or deamortization when individual latency must remain bounded.