Average case versus worst case
“Hash table lookups and quicksort are both called fast. What do average-case and worst-case guarantees mean for each, and when does the difference matter?”
What this tests
- Whether the candidate can state precisely what "expected O(1)" assumes.
- Understanding of why quicksort is
O(n^2)worst case and how randomization changes the guarantee. - Judgement about when worst-case bounds are required (adversarial input, latency SLAs).
Strong answer
A Hash Table lookup is expected O(1) assuming a good hash function and a bounded load factor: keys spread evenly across buckets so chains stay short. Worst case is O(n) when every key lands in one bucket — which happens by bad luck rarely, but by design easily if an attacker chooses keys. Languages mitigate with randomized hash seeds and, in Java, by converting long chains into balanced trees (Separate Chaining with tree bins gives O(log n) worst case).
Quick Sort is O(n log n) on average because a random pivot splits the array reasonably evenly with high probability. Worst case is O(n^2) when the pivot is always an extreme value — deterministic first-element pivot on sorted input. Randomizing the pivot turns the guarantee into "expected O(n log n) for any input", which is different from "average over random inputs". Introsort adds a fallback to heap sort when depth exceeds 2 log n to obtain a hard worst-case bound.
The difference matters when input can be adversarial (public APIs, hash-flooding attacks), when a single slow operation is unacceptable (real-time systems, tail latency), or when correctness depends on the bound (a timeout). For typical interview problems it does not, and a strong candidate says so while proving they know the failure modes.
Green flags · Red flags
- States the assumptions behind expected
O(1)explicitly. - Distinguishes "average over inputs" from "expected over the algorithm's own randomness".
- Knows concrete mitigations: randomized pivot, introsort, hash seed randomization, tree bins.
- Says when worst-case guarantees are worth paying for.
- Says hash tables are "O(1), period".
- Cannot name an input that makes quicksort quadratic.
- Believes randomizing the pivot changes the worst case to
O(n log n).
Follow-up questions
Each follow-up changes a requirement; the right answer changes with it.
O(log n) lookup with ordering. What replaces the hash table?