What is the average time complexity of search in a well-designed hash table with a low load factor?
Correct answer D. O(1)
Explanation
With a good hash function spreading keys uniformly and the load factor kept bounded by resizing, each lookup inspects only a constant expected number of slots or chain entries, so the average cost is O(1). In the worst case, when many keys collide, a search can degrade to O(n). Logarithmic time is typical of balanced search trees, which keep keys in order.
Answer checked How we write and check questions
Discussion