Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Wikipedia has a different sum with a proof that it's $O(k)$. –  Peter Taylor Dec 22 '11 at 9:50
    
Thank you but I am currently interested in binomial (not binary) heaps. –  Dušan Rychnovský Dec 22 '11 at 10:32
add comment

2 Answers

up vote 9 down vote accepted

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

share|improve this answer
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)$. –  Jonas Meyer Dec 22 '11 at 9:02
add comment

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.

share|improve this answer
    
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$. –  Elvis Dec 22 '11 at 13:03
    
@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. –  Srivatsan Dec 22 '11 at 14:22
    
Oups, my mistake, its even better. –  Elvis Dec 22 '11 at 14:38
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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