Searching for an element in the hash table requires O(1) time for the ________…
2014
Searching for an element in the hash table requires O(1) time for the ________ time, whereas for direct addressing it holds for the ________ time.
- A.
worst-case, average
- B.
worst-case, worst-case
- C.
average, worst-case
- D.
best, average
Attempted by 522 students.
Show answer & explanation
Correct answer: C
Answer: average, worst-case
Explanation: Hash table (average) — With a good hash function and a bounded load factor, the expected number of elements examined during a search is constant, so lookup takes O(1) average (expected) time. Collisions are handled by chaining or open addressing, and under typical random/uniform hashing assumptions the average cost remains constant.
Hash table worst-case: if many keys collide (e.g., all map to the same bucket), a search may require scanning all elements, giving O(n) in the worst case.
Direct addressing worst-case: direct addressing stores items in an array indexed by key, so lookup is a single array access and thus O(1) in the worst case (a guaranteed bound).
Summary: The correct wording is that a hash table supports O(1) lookup on average (expected), whereas direct addressing guarantees O(1) lookup in the worst case.