Algorithms and Data Structures · Senior · Question 50 of 75
Which statement about average and worst case of hash table operations is correct?
- ✓Correct answer: Average O(1) assumes a good hash; the worst case is still O(n)
- 2Both average and worst case are O(1) in modern engines
- 3Both are O(log n), because buckets are trees
Explanation
Expected O(1) relies on keys spreading evenly. Some implementations (Java 8 HashMap) turn long chains into trees, bounding the worst case at O(log n), but in general a hash table promises only average-case speed.