Best, average, worst and amortised cost

What is the complexity? hides four questions. Answer the one being asked.

• Best case — the luckiest input. Rarely interesting; it flatters bad algorithms.
• Worst case — the unluckiest input. This is the default, and the only honest number for anything user-facing or security-sensitive.
• Average case — over a realistic distribution of inputs.
• Amortised — the average cost per operation across a long sequence, including the occasional expensive one.

Where they diverge

Linear search: best O(1) when the target is first, worst O(n) when it is last or absent, average O(n/2) = O(n).

Quicksort: average O(n log n), worst O(n²) when the pivot is always the extreme. That worst case is real — feeding sorted data to a naive first-element pivot hits it every time, which is why production sorts randomise the pivot or fall back to a different algorithm.

Hash map lookup: average O(1), worst O(n) if every key collides into one bucket. An attacker who can choose your keys can force that, which is why hash functions in web servers are seeded randomly.

Amortised: the dynamic array

push occasionally has to allocate a bigger array and copy everything. That copy is O(n). Yet everyone calls push O(1), and they are right.

The trick is that the array doubles in size. Starting from capacity 1, growing to n costs 1 + 2 + 4 + … + n copies, which sums to less than 2n. Spread across n pushes, that is a constant amount of copying per push.

const items = [];
for (let i = 0; i < 1_000_000; i++) items.push(i);
// A handful of resizes across a million pushes: O(1) amortised each.

Amortised O(1) means cheap on average across the sequence, not cheap every time. A single push can still stall, which matters for latency-sensitive code even though the throughput number looks fine.

In an interview

Say which case you are quoting. "Average O(1), worst O(n) if the hash degenerates" is a complete answer; "O(1)" alone invites the follow-up you just failed to pre-empt.