Question

What is the time complexity of search function in a hash table using a doubly linked list?

(a) O(1)

(b) O(n)

(c) O(log n)

(d) O(n log n)

This interesting question is from Hash Tables in section Hash Tables of Data Structures & Algorithms I

I have been asked this question in examination.

Answer 1

Right answer is (a) O(1)

To explain: Time complexity of search function in a hash table is O(1). Condition is that the number of collisions should be low.