Explain the difference between amortized, average, and worst-case complexity using Java collections as examples.

## 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 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 fills, it doubles capacity and copies all `n` elements (O(n)). But doubling means that O(n) copy happens only after ~n cheap appends, so summed over `m` appends the total work is O(m), i.e. **O(1) per append on average across the sequence**. 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), or a treeified HashMap with Comparable keys) trades a bit of average speed for a predictable ceiling. - **Security:** because average-case relies on input assumptions, any externally-controlled keys flowing into a HashMap are an attack surface (hash-flooding). Mitigations include randomized seeds, treeification, or switching to ordered/keyed structures with worst-case guarantees. ## 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.