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

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

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

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

7. Solved

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