Search code examples
algorithmbig-onotation

How to find big-oh running time of inserting into a min heap?


I have the following questions:

"Using big-Oh notation, give the running time of inserting the integers 1, 2, 3, · · · , n into an initially empty min heap in the order 1, 2, 3, · · · , n."

"Using big-Oh notation, give the running time of inserting the integers 1, 2, 3, · · · , n into an initially empty min heap in the order n, n-1, n-2,...2, 1."

"Using big-Oh notation, give the running time of inserting integers 1, 2, 3, · · · , 2n in the order 1, n+1, 2, n+2, 3, n+3, · · · , n−1, 2n−1, n, 2n. E.g., if n = 4, then the order of insertions would be 1, 5, 2, 6, 3, 7, 4, 8."

How do I tackle these problems? Is there a simple way to determine running time/big oh notation based on whats inserted?


Solution

  • For min heap you add new element to an end of heap, and push it up, if its smaller than parent, hence:

    1. You add bigger element each time so you do not push anything up so each time you do O(1), and overall is n*O(1)
    2. You add each time smaller element that was on heap before, so you need to bubble it up till the peak, so each time you execute O(log n), so overall is n*O(log n).
    3. In last example you have combined cases 1 and 2, so once you execute O(logn) insretion and once O(1), so overall is sth like: n/2*O(logn) + n/2*O(1).