Questions / Quant development, Algorithms & structures
Average lookup is not a hard deadline
A hash table is described as expected O(1) lookup. Can an individual lookup still be slow?
Answer it in the app It's free. You get hints, a second try if you miss, and a follow-up question.
Show the answer and worked solution
Answer: C. Yes; expected cost permits slow lookup outliers.
- A lookup can be cheap on average while a rare collision chain is expensive. Expected complexity does not prohibit that chain.
- Even a bounded abstract operation count would need a hardware and scheduling model before becoming a strict time bound.
Interview shortcut. Expected O(1) still allows slow outliers.
Takeaway. Separate expected work from worst-case elapsed time.
Why the other choices fail
- No; expected O(1) bounds worst-case probes. Expectation averages over the relevant randomness or workload. It does not bound the slowest possible lookup.
- No; integer keys eliminate collisions and memory-access delays. Integer keys can still collide, and cache misses or contention still affect elapsed time.
- Yes; lookups degrade to O(log n) once the table is half full. Load factor raises average probe counts but does not turn lookups into O(log n). An expected bound simply allows rare slow outliers.
In the app this has a follow-up where one thing about the setup changes. Try the follow-up.