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.

$\endgroup$
2

2 Answers 2

Reset to default
9
$\begingroup$

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

$\endgroup$
1
  • 7
    $\begingroup$ +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)$. $\endgroup$
    – Jonas Meyer
    Dec 22, 2011 at 9:02
9
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – Elvis
    Dec 22, 2011 at 13:03
  • $\begingroup$ @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. $\endgroup$
    – Srivatsan
    Dec 22, 2011 at 14:22
  • $\begingroup$ Oups, my mistake, its even better. $\endgroup$
    – Elvis
    Dec 22, 2011 at 14:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .