0
$\begingroup$

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).

$\endgroup$
2
  • $\begingroup$ It is Stirling's approximation or you can write $\leq n \cdot \log n$ directly. $\endgroup$ Sep 20, 2023 at 13:47
  • $\begingroup$ "which is nowhere close": what ?? $\endgroup$
    – user16034
    Sep 20, 2023 at 14:16

1 Answer 1

2
$\begingroup$

$$\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.

$\endgroup$
1
  • $\begingroup$ Thank you for the formula, now I see it. $\endgroup$
    – bbasaran
    Sep 20, 2023 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.