Results 1 to 7 of 7

Math Help - Sum of log(i) up to n = O(nlogn)

  1. #1
    Newbie
    Joined
    Jan 2010
    Posts
    1

    Question 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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Black's Avatar
    Joined
    Nov 2009
    Posts
    105
    \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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Wondering around the solution

    Any other tips ?
    I do not want the solution but I am still searching hard
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by euloiix View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Question

    Thank you for your reply.
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by euloiix View Post
    Thank you for your reply.
    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jul 2010
    Posts
    3

    Solved

    Thank you for your help. It seems so obvious once you get every steps of reasonning. You have been really helpful.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum