What is the run time efficiency of delete-min operation?

Category: QuestionsWhat is the run time efficiency of delete-min operation?
Editor">Editor Staff asked 1 month ago

What is the run time efficiency of delete-min operation?
 
(a) O(log N)
 
(b) O(logd N)
 
(c) O(d logd N)
 
(d) O(d)
 
Origin of the question is Heap in section Heap of Data Structures & Algorithms I
 
I have been asked this question in an online interview.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct answer is (c) O(d logd N)
 
Explanation: The run time efficiency of a delete-min algorithm using d-1 comparisons is mathematically found to be O(d logd N).