What is the time complexity to delete an element from the direct address table?

Category: QuestionsWhat is the time complexity to delete an element from the direct address table?
Editor">Editor Staff asked 1 month ago

What is the time complexity to delete an element from the direct address table?
 
(a) O(n)
 
(b) O(logn)
 
(c) O(nlogn)
 
(d) O(1)
 
Question is taken from Direct Addressing Tables in chapter Hash Tables of Data Structures & Algorithms I
 
I have been asked this question during an internship interview.

1 Answers
Editor">Editor Staff answered 1 month ago

Right choice is (d) O(1)
 
The explanation is: As every key has a unique array position, it takes constant time to delete an element, although the deleted position must be specified by nil.