Reading Big O as the Worst Case

Big O is an upper bound on a cost function, and every case has its own cost function, so "O(1)" on its own does not say which case it describes. Reading every Big O as a worst-case guarantee is the mistake. This card shows where that reading fails, what it costs, and how to state a cost so it cannot be misread.

A service looks up user records in a hash table, a structure that turns each key into a position in an array. Its documentation says lookups are O(1). On most days the service is fast. On one batch of input it slows to a crawl, and nothing in the code changed.

The O(1) was never a worst-case claim. A hash table sorts keys into buckets, the slots of its array, and a lookup searches one bucket. When the keys spread evenly, a bucket holds about one key, and the expected cost is O(1). When two keys land in the same bucket, a collision, the lookup must search both. If every key collides, a lookup searches all n of them and costs O(n). Both costs are Big O; they describe different cases.

The misreading costs most where the worst case can be reached on purpose. Someone who chooses the keys can make them collide and turn every lookup into a scan of the whole table. That attack is why Python has randomised how it hashes strings since version 3.3, so an outsider cannot predict which keys collide.

State the case beside the bound whenever the cases differ: O(1) expected, O(n) in the worst case. When you read a cost with no case, ask which one it is before you rely on it.