1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Prove that log(n!) ∈ Θ( nlog(n) )

  1. Mar 11, 2012 #1

    s3a

    User Avatar

    1. The problem statement, all variables and given/known data
    The question and solution are in the attachment.


    2. Relevant equations
    Big O, Ω, Θ definitions. Also, I think logarithmic identities.


    3. The attempt at a solution
    It's the part shown in red that I am stuck at. I tried to expand log(n!) to log(n) + log(n-1) + ... + log(1) but I can't see how to get log(n) + log(n-1) + log(n-2) + ... + log(n/2 + 1) + log(n/2) + ... + log(2) + log(1) = n/2 * log(n/2) + n/2 * log(1) out of that.

    Any help getting past this step would be greatly appreciated!
    Thanks in advance!
     

    Attached Files:

    • P5.jpg
      P5.jpg
      File size:
      85.8 KB
      Views:
      120
  2. jcsd
  3. Mar 11, 2012 #2

    rcgldr

    User Avatar
    Homework Helper

    The book isn't stating those are equal instead it's stating it's greater than or equal:

    log(n) + log(n-1) + log(n-2) + ... + log(n/2 + 1) + log(n/2) + ... + log(2) + log(1) >= n/2 * log(n/2) + n/2 * log(1)
     
  4. Mar 11, 2012 #3

    s3a

    User Avatar

    Thanks for clarifying that it's an inequality but I'm still confused as to the reasoning with all the n/2 terms as well as why those curly braces are being chosen in their entirety (because that seems to imply that it's exactly equal to the thing under each respective curly brace).

    If I am being unclear, please tell me.
     
  5. Mar 11, 2012 #4

    rcgldr

    User Avatar
    Homework Helper

    It's because a list of n terms from 1 to n was separated into two lists, {1 to n/2} {n/2+1 to n}.

    Not equal but greater than or equal. For example {log(1) + log(2) + ... + log(n/2)} is greater than {log(1) + log(1) + ... + log(1)}.
     
    Last edited: Mar 12, 2012
  6. Mar 14, 2012 #5

    s3a

    User Avatar

    Okay, I now see that the goal was to choose the smallest (or even a smaller) term from each curly brace such that it's less than or equal to the initial log(n!).

    I am now stuck at the step:
    n/2 [log(n) - 1] >= n/2 [log(n) - 1/2 * log(n)]

    How do I justify that step?
     
  7. Mar 14, 2012 #6

    rcgldr

    User Avatar
    Homework Helper

    It's ok up to this point:

    n/2 log(n/2) + n/2 log(1), since log(1) == 0, this becomes
    n/2 log(n/2) + 0 == n/2 log(n/2)

    n/2 log(n/2) ==
    n/2 (log(n) - log(2))

    Then there's an issue:

    n/2 (log(n) - log(2)) ?= n/2 (log(n) - 1)

    This means log(2) == 1, which is only true if this is log base 2 (log2(...)

    So ignoring this substitution and continuing

    n/2 (log(n) - log(2))

    note that 1/2 log(4) == log(2), { since sqrt(4) == 2, so 1/2 log(4) == sqrt(log(4)) == log(2) }

    if n >= 4, then 1/2 log(n) >= log(2) and

    n/2 (log(n) - log(2)) >= n/2(log(n) - 1/2 log(n))

    since log(n) - 1/2 log(n) = 1/2 log(n),
    n/2(log(n) - 1/2 log(n)) = n/2(1/2 log(n)) = 1/4 n log n
     
    Last edited: Mar 14, 2012
  8. Mar 15, 2012 #7
    Basically the question is prove: lim n->infty log(n!)/ (nlog(n)) = c, for some constant c.
    If you expand n! you get n*(n-1)*(n-2)...etc, which will be n^n-O(n^(n-1)). For large n, n^n will be the dominant term.
     
  9. Mar 17, 2012 #8

    s3a

    User Avatar

    Thanks for the answers.

    rcgldr, the whole 1/2 log(4) == log(2) thing was just an attempt to match my teacher's solution, right?

    For example, if I replaced log(2) with log 1/4 * log(16) instead of replacing it with 1/2 * log(4) and then replaced log(16) with log(n) as follows:
    n/2 * [log(n) - 1/4 * log(n)]
    = 4n/8 log(n) - n/8 log(n)
    = 3/8 * n * log(n)

    it would be a correct yet slightly different approach to what the teacher did, right?
     
  10. Mar 17, 2012 #9

    rcgldr

    User Avatar
    Homework Helper

    Yes, but in this case only if n >= 16.
     
  11. Mar 18, 2012 #10

    s3a

    User Avatar

    I have another mini-question: Is the ending of the solution provided a typo?

    More specifically, should n log(n) <= 4 n log(n) be n log(n) <= 4 log(n!) instead?
     
  12. Mar 18, 2012 #11

    rcgldr

    User Avatar
    Homework Helper

    That's what I think it should be.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Prove that log(n!) ∈ Θ( nlog(n) )
Loading...