online advertising

Wednesday, November 25, 2015

Algorithms: Design and Analysis, Part 1 - Exam Question 6

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.

2 comments:

  1. Your answer is wrong, It takes O(logn) and O(logn) respectively.

    ReplyDelete
    Replies
    1. You are right, I updated the post, I must be out of my mind when I wrote that. Thanks for pointing out!

      Delete