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(\log n) $ time.
Extract-Min takes $ O(\log n) $ time.
Note that the problem is a little sloppy here, it requires an answer in $ \Theta $, 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(\log n) $ time.
Extract-Min takes $ O(\log n) $ time.
Note that the problem is a little sloppy here, it requires an answer in $ \Theta $, 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