Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Can somebody look over my proof? (Asymptotic notation and algorithms)

  1. Jul 16, 2012 #1
    Hey. I'm self studying my way through an algorithms book, and one of the questions at the end of a section is to prove that [itex] log(n!) \in \Theta (n log(n))[/itex]. I wrote up what I believe is a valid proof. However, I don't have much experience writing formal proofs (and even less experience with having my proofs corrected by professionals), so it could very well be invalid/lingered with errors. Can somebody take a quick look at it and comment on any mistakes that may exist? Can you comment on my style? Any advice would be appreciated.

    Here is my write-up. I apologize for not using the built-in equation editor.

  2. jcsd
  3. Jul 17, 2012 #2
    I think Stirling's formula is unnecessary here. An asymptotic expression for [itex]\log(n!)[/itex] can be obtained as follows:
    [tex]\log(n!)=\sum_{k=1}^{n}\log(k) \sim \int_{1}^{n}\log(x)dx[/tex]
    The integral on the right side can be evaluated using integration by parts:
    [tex]\int \log(x)dx = x\log(x) - \int dx = x\log(x)-x+C[/tex]
    and this yields
    [tex]\log(n!) \sim n\log(n)-n \sim n\log(n)[/tex]
    Can you take it from there?
  4. Jul 17, 2012 #3
    That wouldn't be rigorous, would it? In my proof, I kept the error terms and treated them rigorously.

    EDIT: The point of the problem is to proof the asymptotic behavior of the function, so it would be self defeating to use its asymptotic form. Please correct me if I am wrong, though.
    Last edited: Jul 17, 2012
  5. Jul 17, 2012 #4


    User Avatar
    Science Advisor
    Homework Helper

    You can get the error bounds from post #2.
    $$\log(n!) = \sum_{k=2}^n \log k$$
    I changed the lower limit since ##\log 1 = 0##.

    Because ##\log## is a monotonic function you can bracket the sum by two integrals
    $$\int_2^n \log (x-1)\,dx < \sum_{k=2}^n \log k < \int_2^n \log x\,dx$$

    Draw a picture of the integrals and the sum as a set of rectangles, if you can't see where that came from.
  6. Jul 17, 2012 #5
    I see! That definitely looks like a valid proof, too. The book that I'm using mentioned bounding functions using integrals, but for some reason told me to use Sterling's formula to prove the theorem.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook