The worst case complexity of deleting any arbitrary node value element from heap is __________

Category: QuestionsThe worst case complexity of deleting any arbitrary node value element from heap is __________
Editor">Editor Staff asked 1 month ago

The worst case complexity of deleting any arbitrary node value element from heap is __________
 
(a) O(logn)
 
(b) O(n)
 
(c) O(nlogn)
 
(d) O(n^2)
 
My question is taken from Heap topic in chapter Heap of Data Structures & Algorithms I
 
This question was posed to me in an interview for internship.

1 Answers
Editor">Editor Staff answered 1 month ago

The correct choice is (a) O(logn)
 
Easy explanation – The total possible operation in deleting the existing node and re locating new position to all its connected nodes will be equal to height of the heap.