The math behind the time complexity of Heap Insertion

Question

Insertion into a heap is an O(logn) operation. Insertion of n elements into a heap one by one is summarised as O(n * logn). I wonder about the math behind this, because I could not reach to the same outcome.

Let's say we have an empty heap h = [].

• The first insertion will be a constant time operation, say O(1)
• The second insertion will also be O(1), because there was only one element in the heap
• The third will be O(log2) and so on

So if we write it down, the overall time complexity will be:

O(1 + 1 + log2 + log3 + ... + log(n-1)) = O(2 + log(n - 1)!) = O(logn!) approximately, which is nowhere close to O(n * logn).

Answer 1

$$\ln(n!)=\ln\left(\prod_{k=1}^nk\right)=\sum_{k=1}^n\ln(k)\approx\int_{k=0}^n\ln(t)\,dt=(t\ln(t)-t)\Big|_{t=0}^n=n\ln(n)-n.$$

One can show that the approximation error does not impact the asymptotic behavior.