Time complexity of inserting into a heap under 3 different situations

Question

I know that in the case of inserting numbers 1,2,3,......,n into a initially empty min heap with the order 1,2,3,.....,n, you will just need to put them in one-by-one. But I can't quite work out how to calculate the time complexity of two different cases: if you insert them in a reverse order (n,n-1,n-2,....,2,1) or even with other numbers with the order (1,n+1,2,n+2,3,n+3,....,n-1,2n-1,n,2n). I know that for the reverse case, you will have to move the numer inserted "along" the height of the heap (which is logn) but I am not quite sure about the remaining parts...

Answer 1

As you say, when you insert the numbers 0..n in-order into a min-heap, insertion is O(1) per item. Because all you have to do is append the number into the array.

When you insert in reverse order, then every item is inserted into the bottom row, and has to be sifted up through the heap to the root. Every insertion has to move up log(n) rows. So insertion is O(log n) per item.

The average, when you're inserting items at random, as discussed at some length in Argument for O(1) average-case complexity of heap insertion and the articles it links, is something like 1.6.

So there is a very strong argument that the average complexity of binary heap insertion is O(1).

In your particular case, your insertions are alternating O(1) and O(log n). So over time you have O((1+log n)/2), which is going to be O(n log n) to insert all of the items.