Searching for an element in the hash table requires O(1) time for the ________ time, whereas for direct addressing it holds for the ________ time.
UGC NET - 2014,
Answer: C
A hash table searches in O(1) time on the average, and direct addressing searches in O(1) time in the worst case. With hashing, collisions can make a search take longer in the worst case, but with good hashing the expected time is constant. With direct addressing, the key is the index of the table, so a search is one access even in the worst case. The other options invert this or name a best case, which is not the standard comparison. Direct addressing needs a table with one slot for every possible key, which is why its search time does not vary, whereas a hash table maps many keys to a smaller table and so can have collisions.
Please log in or register to report this question.