Amortized Complexity — Why ArrayList.add and HashMap.put Are Really O(1)
Fast recall
Quick revision
Core answer
ArrayList.add(e) can be O(1) (just drop the value into the next array slot) or O(n) (when capacity is exceeded, allocate a bigger array and copy all existing elements). The worst-case single operation is O(n) — but it's so rare that, averaged across all adds, the cost per add is O(1). This is called amortized O(1). Proof by aggregate analysis: ArrayList doubles capacity when full (default growth factor 1.5x in Java, but doubling is easier to analyze). For n adds starting from capacity 1, total resize work is 1 + 2 + 4 + ... + n/2 = n - 1 element copies plus n inserts — total 2n − 1 ops = O(n), divided by n adds = O(1) per add. Same pattern for `HashMap.put`: when load factor exceeds 0.75, the internal table doubles and every entry is rehashed into the new table — one put can be O(n) — but the cost averages to O(1) per put. Why it matters: you can treat list.add() and map.put() as cheap in algorithm analysis, even knowing individual ops can occasionally block. The trade-off: amortized bounds hide worst-case latency; if you need predictable per-op latency (real-time systems, low-latency trading), amortized O(1) isn't good enough — pre-size the collection (new ArrayList<>(knownCapacity)) to avoid resize. Three amortization techniques exist: aggregate (total cost / n), accounting method (charge extra 'credit' to cheap ops to pay for expensive ones), and potential method (formal analysis via a potential function). For interviews, the aggregate argument is usually enough.Whether the candidate understands amortized analysis (not just 'average case'), can prove ArrayList.add is amortized O(1) via the doubling argument, and knows when amortization isn't good enough
Confusing amortized with average-case (they're different concepts). Not knowing why doubling (vs adding a fixed amount) gives O(1) amortized. Claiming a single ArrayList.add is always O(1)
Give the aggregate analysis proof, mention the three techniques (aggregate / accounting / potential method), discuss why low-latency systems avoid amortization, and reference Java's actual 1.5x growth factor
Interview-ready guide
Interview answer
Amortized complexity is the average cost per operation over a long sequence, accounting for occasional expensive operations spread across many cheap ones.
ArrayList.add — the canonical example
- Single
add(e): usually O(1) (drop value into next array slot) - When capacity is exceeded: O(n) (allocate bigger array, copy all elements)
- Worst-case single op: O(n)
- But amortized across all adds: O(1)
Why? The doubling argument
- ArrayList grows ~1.5x when full (Java default)
- For simpler math, assume doubling
- Starting from capacity 1, after n adds, resizes happen at sizes 1, 2, 4, 8, ..., n/2
- Total resize cost: 1 + 2 + 4 + ... + n/2 ≈ n element copies
- Total insert cost: n
- Total over n adds: ~2n = O(n)
- Amortized per add: O(n) / n = O(1)
Why doubling, not fixed increments?
- If we grew by +10 each time: resizes at 10, 20, 30, ...
- Total copy work: 10 + 20 + ... + n = O(n²)
- Amortized: O(n) per add — bad
- Multiplicative growth (1.5x, 2x) is essential for O(1) amortized
- All resizable arrays use this: Java ArrayList, Go slices, Python lists, C++ vectors
HashMap.put — same story
- When size ≥ capacity × load factor (0.75 default), rehash
- One put: O(1) normal, O(n) during resize
- Amortized: O(1)
Amortized vs average-case vs worst-case
Worst-case: max cost of a single operation
- ArrayList.add: O(n)
Average-case: expected cost over probability distribution of inputs
- HashMap.get: O(1) with good hash
Amortized: average per op over a sequence, worst-case guarantee
- ArrayList.add over n ops: total O(n) ALWAYS, no matter input
Key difference: amortized is a guarantee; average-case is probabilistic.
Three formal techniques
1. Aggregate analysis (simplest, interview-friendly)
- Total cost of n ops: T(n)
- Amortized per op: T(n) / n
- ArrayList: T(n) = 2n → O(1) amortized
2. Accounting method (banker's)
- Charge each op more than actual cost
- Extra credit prepays for expensive ops
- For ArrayList: charge 3 per add — enough to cover future resize
3. Potential method
- Define a potential function Φ over the data structure state
- Amortized cost = actual cost + ΔΦ
- Most formal, used in research
For interviews: aggregate is sufficient.
When amortized is not enough
Real-time systems
- Trading, avionics, robotics
- p99/p999 latency SLAs can't tolerate occasional O(n) blips
- Solution: pre-size to avoid resize
new ArrayList<>(expectedSize)ornew HashMap<>((int)(n / 0.75f) + 1)
Concurrent systems
- Amortized bounds assume single-thread
- ConcurrentHashMap uses incremental resize to avoid blocking
- Segment-based (Java 7) or fully concurrent (Java 8+)
Memory-constrained systems
- 1.5x growth wastes ~25% space on average
- Use
ArrayList.trimToSize()to reclaim - Or use fixed-size arrays if size is known
Pre-sizing to avoid amortization
List<Integer> list = new ArrayList<>(expectedSize);
for (int i = 0; i < expectedSize; i++) list.add(i);
// No resize — every add is O(1) worst caseKey takeaways
1. Treat ArrayList.add and HashMap.put as O(1) in algorithm analysis
2. Know that a single op can be O(n) under resize
3. Pre-size when you know the size — especially for hot paths and large batches
4. Say 'amortized O(1)' explicitly — not just 'O(1)' — shows depth in interviews
5. Amortization hides worst-case latency — real-time systems need different strategies
Recommendation: In interviews, when asked about ArrayList.add or HashMap.put, say 'amortized O(1)' explicitly — not just 'O(1).' Explain with the doubling argument: 'n adds cost 2n total element copies because each resize doubles the capacity, so resizes are exponentially rarer. The geometric sum 1 + 2 + 4 + ... + n/2 is bounded by n.' Distinguish amortized from average-case: amortized is a worst-case guarantee over a sequence; average-case assumes a probability distribution. For production code: pre-size collections when the size is knowable (new ArrayList<>(n), new HashMap<>((int)(n / 0.75f) + 1)) — this eliminates resize entirely and gives you true per-op O(1). For real-time / low-latency systems, amortized isn't good enough; use pre-sized or bounded collections, profile p99 latency, and consider ConcurrentHashMap which uses incremental resize. For interviews at trading or systems firms, knowing the three techniques (aggregate, accounting, potential method) marks you as advanced — though aggregate is usually sufficient. The mental model: amortization spreads occasional big costs across many small ones; it's a mathematical accounting trick that lets us reason about collections as if they're always cheap, while the implementation quietly handles the occasional expensive moment.
Amortized Complexity — Why ArrayList.add and HashMap.put Are Really O(1)
Direct Answer
Amortized complexity is the average cost per operation over a long sequence, accounting for occasional expensive operations spread across many cheap ones. A single ArrayList.add(e) can be O(1) (just drop the value into the next array slot) or O(n) (when capacity is exceeded, allocate a bigger array and copy all existing elements). The worst-case single operation is O(n) — but it's so rare that, averaged across all adds, the cost per add is O(1). This is called amortized O(1). Proof by aggregate analysis: ArrayList doubles capacity when full (default growth factor 1.5x in Java, but doubling is easier to analyze). For n adds starting from capacity 1, total resize work is 1 + 2 + 4 + ... + n/2 = n - 1 element copies plus n inserts — total 2n − 1 ops = O(n), divided by n adds = O(1) per add. Same pattern for HashMap.put: when load factor exceeds 0.75, the internal table doubles and every entry is rehashed into the new table — one put can be O(n) — but the cost averages to O(1) per put. Why it matters: you can treat list.add() and map.put() as cheap in algorithm analysis, even knowing individual ops can occasionally block. The trade-off: amortized bounds hide worst-case latency; if you need predictable per-op latency (real-time systems, low-latency trading), amortized O(1) isn't good enough — pre-size the collection (new ArrayList<>(knownCapacity)) to avoid resize. Three amortization techniques exist: aggregate (total cost / n), accounting method (charge extra 'credit' to cheap ops to pay for expensive ones), and potential method (formal analysis via a potential function). For interviews, the aggregate argument is usually enough.
Common Mistakes & Pitfalls
Confusing amortized with average-case (they're different concepts). Not knowing why doubling (vs adding a fixed amount) gives O(1) amortized. Claiming a single ArrayList.add is always O(1)
Check your understanding
Answer these without looking back at the article.
- Why does `ArrayList` use multiplicative growth (1.5x) instead of a fixed increment?
- What's the difference between amortized complexity and average-case complexity?
- When is amortized O(1) not good enough?
- How do you avoid resize in ArrayList or HashMap?
- How does ConcurrentHashMap handle resize without blocking all threads?
Related interview prep categories
1Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.