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

Category: QuestionsWhat is the time complexity of delete function in the hash table using a doubly linked list?
Editor">Editor Staff asked 1 month ago

What is the time complexity of delete function in the hash table using a doubly linked list?
 
(a) O(1)
 
(b) O(n)
 
(c) O(log n)
 
(d) O(n log n)
 
This key question is from Hash Tables in portion Hash Tables of Data Structures & Algorithms I
 
This question was addressed to me during an online exam.

1 Answers
Editor">Editor Staff answered 1 month ago

Right option is (a) O(1)
 
The best explanation: 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.