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?
For min heap you add new element to an end of heap, and push it up, if its smaller than parent, hence: