Algorithmic Foundations
Amortized Analysis
Amortized analysis bounds the average cost per operation over a worst-case sequence of operations, even when individual operations occasionally cost much more than that average.
- A single expensive operation is fine if it is rare enough that cheap operations pay for it over the whole sequence
- Dynamic array growth (
ArrayList.add) isO(1)amortized: doubling capacity makes resizes exponentially rarer as the array grows - The accounting method: overcharge cheap operations a little, bank the credit, spend it on the rare expensive one
- Amortized bounds are about a sequence starting from empty — a single worst-case call can still be
O(n) - Different from average-case analysis: amortized bounds require no assumption about input distribution, only about the operation sequence
When an ArrayList (see Arrays And Linked Lists) is full and add is called, it allocates a new backing array — typically 1.5–2× the size — and copies every existing element, an O(n) operation. Naively this looks like n calls to add could cost O(n²) total. It does not, because resizes happen at sizes 1, 2, 4, 8, 16, ... — geometrically rarer — so the total copying work across n inserts is a geometric series summing to O(n), i.e. O(1) amortized per add.
// Charge $3 per add(): $1 pays for the insert itself,
// $2 is banked as credit on the newly-inserted element.
// When the array of size k doubles to 2k, the resize must copy k elements;
// those k elements each still hold their $2 credit -> exactly $2k available,
// covering the O(k) copy with $0 left over. Credit never goes negative,
// so the $3 flat rate is a valid amortized bound: add() is O(1) amortized.| Operation | Worst single call | Amortized over n calls |
|---|---|---|
add (append) | O(n) — on resize | O(1) |
add(i, e) (middle) | O(n) — shift | O(n) (no amortized win — every call shifts) |
get(i) / set(i, e) | O(1) | O(1) |