in the given quiz question 2 as the question says best complexity for deletion in min heap should be O(n)
according to answer but i have the doubt that it should be O(logn) since the best case would be when the root will be deleted and downheapification would be called.
how it can be O(n)???
Doubt regarding the best complexity of deletion in min heap
@sharad1103
Yes you are right, but you also have to go to the element that you want to delete. To get that element in we have to traverse the array. which is O(N) and to remove it , it is log n as you mentioned, so it it O(n + log n) which is O(N)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.