What is the difference between amortized, average, and worst-case complexity, using Java collections as examples?
answer
- Worst-case = max single op, hard guarantee
- Amortized = sequence average, can't be broken by input
- Average = expected over input distribution, breakable (adversarial)
- ArrayList add = amortized O(1); HashMap get = average O(1)
- Hash-flooding DoS exploits the average-vs-worst gap
basics
~20 sAmortized cost averages an expensive-but-rare operation over many cheap ones (ArrayList append). Average-case is the expected cost over typical inputs (HashMap get). Worst-case is the most expensive single operation that can happen (a HashMap lookup when colliding keys have no order).
solid answer
~50 sAmortized complexity averages the cost of a sequence of operations so a rare expensive step is spread across many cheap ones — ArrayList.add is amortized O(1) because the occasional O(n) array growth (1.5x in OpenJDK) is paid back by the O(1) appends before it; amortized is a guarantee over a sequence, not a probability. Average-case complexity is the expected cost over a distribution of inputs — HashMap.get is average O(1) assuming well-distributed hashes, a statistical claim that adversarial input can violate. Worst-case is the maximum cost of any single operation — HashMap.get is O(n) when keys share one hash and have no order, and O(log n) in a tree bin whose keys have distinct hashes or are Comparable; a single ArrayList resize is O(n). Amortized bounds are safe for throughput; average bounds can be attacked (hash-flooding DoS); worst-case bounds are what tail-latency SLAs need, which is why latency-critical systems sometimes prefer TreeMap's guaranteed O(log n).
go deeper
Can recognise the words and give one example each (ArrayList append cheap on average, HashMap usually O(1)).
Explains amortized via the ArrayList resize and average via HashMap distribution, and that worst case is the maximum single op.
Articulates that amortized is a per-sequence guarantee while average is a breakable statistical claim, with the HashMap collision example.
Connects the distinction to design: throughput vs tail-latency SLAs and hash-flooding security, justifying guaranteed-worst-case structures when input is adversarial or latency-critical.
## Why there are three kinds of 'complexity' When we say an operation 'is O(f(n))' we should ask *under which assumptions*. The same operation can have very different costs depending on whether we mean the cost of a single unlucky call, the typical cost, or the cost spread over a run of calls. Three precise notions capture this. ## Worst-case complexity The **maximum** cost of a **single** operation over **all possible inputs and states** — a hard guarantee that no call exceeds it. It makes no assumptions about luck or input distribution. - *Example:* `HashMap.get` worst case is **O(n)** — if every key hashes to the same bucket, the lookup scans them all. (Java 8 treeification softens this to **O(log n)** when keys have distinct hash codes or are `Comparable`.) - *Example:* a single `ArrayList.add` that triggers a resize is **O(n)** — it copies the whole backing array. ## Amortized complexity The **average cost per operation over a sequence**, where occasional expensive operations are 'paid for' by many cheap ones. Crucially this is a **guarantee about the total cost of a sequence**, not a probability — it does not rely on lucky inputs. - *Example:* `ArrayList.add` is **amortized O(1)**. Most appends write into a free slot in O(1). When the array is full, OpenJDK grows it by half (preferred growth `oldCapacity >> 1`) and copies all its elements (O(n)). Growing by a constant factor means a copy of `n` elements comes only after about `n/3` cheap appends, so summed over `m` appends the total work is O(m), i.e. **O(1) per append on average across the sequence**. The Javadoc states it as "adding n elements requires O(n) time". This is provable (the 'accounting' or 'potential' method), independent of input values. The key contrast: **amortized is deterministic over a sequence; you cannot construct an input that breaks it.** ## Average-case complexity The **expected** cost of an operation over a **probability distribution of inputs** (often assuming inputs are 'random' or hashes are well distributed). It is a **statistical** claim and can be violated by carefully chosen (adversarial) input. - *Example:* `HashMap.get` is **average O(1)** — assuming hash codes spread keys roughly uniformly, each lookup touches one short bucket. But this assumption can be **deliberately broken**: an attacker who knows the hash function can craft thousands of keys that all collide, forcing O(n) (or O(log n)) per lookup. This is the basis of **hash-flooding denial-of-service** attacks. ## Putting them side by side | Notion | Over what | Guarantee? | Breakable by input? | Example | |---|---|---|---|---| | Worst-case | a single op, any input | yes (upper bound) | n/a (it is the max) | ArrayList resize O(n); HashMap.get O(n) | | Amortized | a sequence of ops | yes (per-sequence) | no | ArrayList.add O(1) | | Average | one op over input distribution | no (expected only) | yes (adversarial) | HashMap.get O(1) | ## Why the distinction is load-bearing in design - **Throughput systems** care about *total* work, so **amortized** bounds (ArrayList append, amortized HashMap insert) are exactly the right lens. - **Tail-latency / SLA-bound systems** care about the *worst single* request. Here HashMap's average O(1) is risky — a rare collision spike or an attacker can blow a p99.9. A structure with a **guaranteed worst case** (TreeMap's O(log n)) trades a bit of average speed for a predictable ceiling. A treeified HashMap bin with Comparable keys bounds lookups the same way, but a `put` can still hit an O(n) resize. - **Security:** because average-case relies on input assumptions, any externally-controlled keys flowing into a HashMap are an attack surface (hash-flooding). `java.util.HashMap` has no per-map hash seed at JDK 27 (JDK 7's optional `jdk.map.althashing.threshold` seed did not survive into JDK 8), so it relies on treeification: attacker-chosen `String` keys are `Comparable`, so they degrade to O(log n) rather than O(n). Other mitigations are capping untrusted input sizes or using a comparison-ordered structure with a worst-case guarantee. ## The senior/principal framing Amortized and average can both 'round to O(1)' yet mean different things: amortized is robust (you can't break it with input), average is probabilistic (you can). Knowing which one a structure offers tells you whether it is safe under adversarial or tail-sensitive conditions — that is the difference between a throughput choice and a latency/security choice.
- ArrayList.add and HashMap.get can both be called 'O(1)' — why is one safer than the other?ArrayList.add is amortized O(1): a guarantee over a sequence that no input can break. HashMap.get is average O(1): a statistical expectation that adversarial keys can degrade to O(n)/O(log n). The amortized bound is robust; the average bound is attackable.
- When would you accept TreeMap's O(log n) over HashMap's average O(1)?When you need a guaranteed worst-case bound — e.g. a tail-latency SLA, or keys from untrusted input where hash-flooding is a risk — and/or you also need sorted/range access. The predictable ceiling can outweigh the faster average.
- Treating amortized and average as the same thing
- Thinking amortized O(1) means every individual operation is O(1)
- Ignoring that HashMap's average case is attackable (hash-flooding)
- Claiming worst-case bounds never matter because the average is good
- HashMap tree bins
- Java 1.8
Assumes JDK 27. ArrayList's 1.5x growth and the tree bins are the same at JDK 25. Tree bins date from Java 8, the release whose HashMap no longer has JDK 7's optional hash seed.
context
- ArrayList (Java SE 27 & JDK 27)docs.oracle.com
- HashMap (Java SE 27 & JDK 27)docs.oracle.com
- HashMap.java at jdk-27-gagithub.com