Average and worst-case lookup in a hash table?
Options
- O(1) on average, O(n) in the worst case (Correct option)
- O(log n) in both the average and worst case
- O(1) in both the average and worst case
- O(n) on average, O(n²) in the worst case
Answer
O(1) average, O(n) worst
Why
A hash table (Python dict or set) computes a hash of the key to jump directly to the right slot, so a lookup takes about the same time no matter how big it is: O(1) on average.
If many keys land in the same slot (collisions), it must check them one by one; in the worst case that is O(n). Good hash functions make this very rare.
Remember
dict/set lookup ≈ O(1).