Exercise 3: What "O(1) Hash Table Lookups" Leaves Out — Possible Solution ==================================================================== WHAT'S MISSING FROM THE CLAIM ------------------------------ The colleague's "O(1)" claim, without qualification, is almost certainly describing the AVERAGE case for hash table lookups, not a guarantee that applies to every possible situation. Per this chapter's own best/worst/average-case distinction, a single Big-O figure quoted in casual conversation like this is easy to mistake for a universal guarantee, when it's actually describing just one specific scenario among several genuinely different ones. THE WORST CASE THAT'S BEING LEFT OUT ------------------------------ Per this chapter's own hash-collision finding, a hash table's WORST case lookup degrades to Theta(n) when many keys collide into the same bucket - a real, well-documented failure mode, not a purely theoretical curiosity. Simply saying "O(1)" glosses over this entirely different, much worse scenario. WHY THIS MATTERS FOR "PERFORMANCE IS NEVER A CONCERN" ------------------------------ Per this chapter's own security-adjacent finding, worst-case behavior isn't just a rare, ignorable edge case - it's specifically what an attacker who can predict or influence key distribution could deliberately trigger, turning a normally fast service into a denial-of-service target by forcing every lookup into its Theta(n) worst case. Dismissing performance as "never a concern" based solely on the average-case figure ignores exactly the scenario where performance concerns would matter most - under adversarial or unusually unlucky conditions, not typical, everyday ones. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation identifies specifically which case (average, not worst) the colleague's O(1) claim actually describes, using this chapter's own case distinction, and connects the omitted worst case directly to this chapter's own hash-collision security finding rather than treating the objection as a purely abstract complaint about imprecise notation.