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

1. ## 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.

2. $\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 $n \ge 1$.

3. ## Wondering around the solution

Any other tips ?
I do not want the solution but I am still searching hard

4. Originally Posted by euloiix
Any other tips ?
I do not want the solution but I am still searching hard
$\log(1)+\log(2)+\cdots+\log(n)=\log(n!)=\ldots$

and use Sterling's Approximation for n!: $\scriptstyle n!\simeq \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$, for $\scriptstyle n\to \infty$. - But Black's solution, to me, seems much better.

5. ## 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.

6. 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

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

Black has shown that

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

From this you get that

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

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

7. ## Solved

Thank you for your help. It seems so obvious once you get every steps of reasonning. You have been really helpful.