5
$\begingroup$

I'm studying time complexity of binomial heaps and there's one operation (the make-heap operation) that does not make sense to me unless the following is true.

$\sum\limits_{i=1}^k \log(i)$ belongs to $O(k)$

Please help me find a proof for that statement.

Any help appreciated.

  • 0
    Thank you but I am currently interested in [binomial](http://en.wikipedia.org/wiki/Binomial_heap) (not [binary](http://en.wikipedia.org/wiki/Binary_heap)) heaps.2011-12-22

2 Answers 2

9

Well, I am sorry but this is an $O\left( \int_1^k \log x\mathrm d x\right)$, and $\int_1^k \log x\mathrm d x = \left[ x\log x - x \right]_1^k = O(k \log k).$

  • 7
    +1. Also, by Stirling's approximation, $\log(k!)\sim \frac{1}{2}\log(2\pi k) +k\log(k)-k=O(k\log k)$, and not $O(k)$.2011-12-22
9

Elvis's answer is nicer than this, but since the question comes from intro algorithms, I'd point out that for many elementary CS applications the trivial bounds like: $ (n/2)\log(n/2) = (n/2)(\log n - 1) \le \sum_{i=1}^n \log i\le n\log n $ are good enough and worth trying if you're just doing homework.

Update: The lower bound here can be obtained by noticing that half of the terms in the sum are at least $\log(n/2)$, since log is monotone. Also, fixed a dropped set of brackets.

  • 0
    Oups, my mistake, its even better.2011-12-22