Amortised analysis: what operations really cost
Best, average and worst case per operation, why a single push onto a dynamic array is sometimes O(n) but still O(1) on average, and why constant factors and cache locality decide real performance.
Three different questions
When someone says an operation is O(1), ask which case they mean. A lookup in a hash table is O(1) expected and O(n) worst case, and both answers are correct about the same code.
| Structure | Operation | Worst case | Amortised / expected |
|---|---|---|---|
| Dynamic array | append | O(n) when it must grow | O(1) amortised |
| Dynamic array | index | O(1) | O(1) |
| Dynamic array | insert at front | O(n) | O(n) — no averaging helps |
| Hash table | get | O(n) with all keys colliding | O(1) expected |
| Balanced tree | insert | O(log n) | O(log n) guaranteed |
| Binary heap | push | O(log n) | O(log n) |
Worst case is the guarantee you need for latency-sensitive paths. Amortised cost is the total divided by the number of operations, and it is the right measure for throughput-oriented work.
Why doubling makes append constant
# geometric growth: capacity doubles
# appends 1..8, cost of the copy
# push 1 -> allocate 1, copy 0
# push 2 -> allocate 2, copy 1
# push 3 -> allocate 4, copy 2
# push 5 -> allocate 8, copy 4
# push 9 -> allocate 16, copy 8
total copy cost after n pushes = n-1 (a geometric series)
amortised cost per push = O(1)Doubling is what makes the series converge. Growing by a constant amount instead gives O(n) amortised append, because the number of copies is proportional to n for every n.
| Growth policy | Copies after n appends | Amortised append | Memory slack |
|---|---|---|---|
| +1 each time | about n squared / 2 | O(n) | None |
| +k constant | about n squared / (2k) | O(n) | Constant |
| x2 | about n | O(1) | Up to 2x |
| x1.5 | about 2n | O(1) | Up to 1.5x, reuses freed memory sooner |
Big-O hides the constant, and the constant is often the answer
// Two ways to sum an array.
// A: sequential — one cache line per 16 ints
for (int i = 0; i < n; i++) sum += a[i];
// B: strided — a new cache line for almost every element
for (int i = 0; i < n; i += 16) sum += a[i];
// Same O(n). B can be several times slower in wall-clock time.- A pointer-chasing structure (linked list, tree of nodes) costs a memory access per step; contiguous data does not.
- Branch mispredictions on unpredictable comparisons can cost more than the comparison itself.
- A linked list of 10,000 small ints is usually slower to traverse than a contiguous array of 100,000 ints.
- Allocation and garbage collection are part of the real cost of node-based structures.
FAQ
Is amortised O(1) good enough for a latency SLA?
Why do libraries use 1.5x rather than 2x growth?
Related
Heaps and priority queues Benchmarking and testing your data structure
Last refreshed 2026-09-18.