Question

What is the time complexity of delete function in the hash table using list head?

(a) O(1)

(b) O(n)

(c) O(log n)

(d) O(n log n)

My question comes from Hash Tables topic in section Hash Tables of Data Structures & Algorithms I

This question was posed to me in final exam.

Answer 1

Correct choice is (a) O(1)

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