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
    Wikipedia has a [different sum](http://en.wikipedia.org/wiki/Binary_heap#Building_a_heap) with a proof that it's $O(k)$.2011-12-22
  • 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
    Well, I think this is very nice; you should precise that the first inequality comes from Jensen inequality. It is nice because it is quick, simple and it applies to a wide range of discrete sums, my method is ok because we have the luck to know a primitive of $\log x$.2011-12-22
  • 0
    @Elvis, The first part does not use Jensen. You only need to note that the last $n/2$ terms in the equality (namely, $\log i$ for $i \geq n/2$) are at least $\log (n/2)$ each.2011-12-22
  • 0
    Oups, my mistake, its even better.2011-12-22