Algorithms and Data Structures · Senior · Question 61 of 75
What is the lower bound for finding an element in an unsorted array, and why?
- 1Ω(log n): with clever probing you can halve it
- 2Ω(1): hashing finds it immediately
- ✓Correct answer: Ω(n): any unchecked position could hold the target
Explanation
An adversary argument: if an algorithm skips a position, the target could be there. Hashing helps only after an O(n) preprocessing step that builds the table.