# Sum of log(i) up to n = O(nlogn)

• Jan 30th 2010, 06:04 PM
Nemo78
Sum of log(i) up to n = O(nlogn)
First, I apologize if this is in the wrong section.

How do I go about demonstrating that the sum of log(i) from i up to n [eg. log(1) + log(2)... + log(n)] = O(n*logn)? That's Big-Oh notation. Any help/tips would be appreciated as I can't think where to start.(Worried)
• Jan 30th 2010, 07:04 PM
Black
$\displaystyle \text{log}(1)+\text{log}(2)+\cdots+\text{log}(n) \le \text{log}(n)+\text{log}(n)+\cdots+\text{log}(n)=n \text{log}(n)$ for all $\displaystyle n \ge 1$.
• Jul 27th 2010, 03:36 AM
euloiix
Wondering around the solution
Any other tips ?
I do not want the solution but I am still searching hard
• Jul 27th 2010, 03:52 AM
Failure
Quote:

Originally Posted by euloiix
Any other tips ?
I do not want the solution but I am still searching hard

$\displaystyle \log(1)+\log(2)+\cdots+\log(n)=\log(n!)=\ldots$

and use Sterling's Approximation for n!: $\displaystyle \scriptstyle n!\simeq \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$, for $\displaystyle \scriptstyle n\to \infty$. - But Black's solution, to me, seems much better.
• Jul 27th 2010, 05:52 AM
euloiix
Question
But it seems that I misunderstood. Are you able to conclude direcly from Black's proposition ?

Can you pass the equivalence to x-> infinity ? I have not done math for a long time but I remember it is not always such a basic thing to do.
• Jul 27th 2010, 06:43 AM
Failure
Quote:

Originally Posted by euloiix
But it seems that I misunderstood. Are you able to conclude direcly from Black's proposition ?

Yes, and easily at that. You need to make sure you understand what you need to show in order to prove that

$\displaystyle \sum_{k=1}^n \log(n) = O(n\log n)$

Black has shown that

$\displaystyle 0\leq \sum_{k=1}^n\log(k) \leq n\log(n)$

From this you get that

$\displaystyle \left|\sum_{k=1}^n\log(k)\right|\leq C\cdot n\log(n)$

for $\displaystyle n\to \infty$, and with C=1, actually.

You really should look up the definition of Landau's Big-Oh notation, and preferably reproduce it without cheating on a white sheet of paper some time later. Definitions are very important in mathematics: without knowing them (or at the very least looking them up) you cannot hope to find the answer to an exercise like this.
• Jul 27th 2010, 07:55 AM
euloiix
Solved
Thank you for your help. It seems so obvious once you get every steps of reasonning. You have been really helpful.