Problem:
What is the asymptotic running time of the Insert and Extract-Min operations, respectively, for a heap with n objects?
Solution:
This is just memorizing the standard results.
Insert takes O(logn) time.
Extract-Min takes O(logn) time.
Note that the problem is a little sloppy here, it requires an answer in Θ, however, in the best case both operation takes just O(1) time, and the problem do not explicitly ask for the worst case time.
What is the asymptotic running time of the Insert and Extract-Min operations, respectively, for a heap with n objects?
Solution:
This is just memorizing the standard results.
Insert takes O(logn) time.
Extract-Min takes O(logn) time.
Note that the problem is a little sloppy here, it requires an answer in Θ, however, in the best case both operation takes just O(1) time, and the problem do not explicitly ask for the worst case time.
Your answer is wrong, It takes O(logn) and O(logn) respectively.
ReplyDeleteYou are right, I updated the post, I must be out of my mind when I wrote that. Thanks for pointing out!
Delete