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$
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$
  • 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 '11 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$
  • $\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 '11 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 '11 at 14:22
  • $\begingroup$ Oups, my mistake, its even better. $\endgroup$ – Elvis Dec 22 '11 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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