📝 Question
#1447
Which of the following scenarios leads to linear running time for a random search hit in a linear-probing hash table?
✓
Correct Answer
A. All keys hash to same index
💡
Explanation
If all keys hash to the same location then the i-th inserted key would need i lookups to be found. The probability of looking up i-th key is 1/n (since it’s random). If you know some probability it’s trivial to show that such lookups have linear time.
⌨️ Press
A
B
C
D
to select