Search code examples
algorithmlogarithm

Proving with stirlling approximation

How do you prove using Stirling's approximation?

           log(n!)=Θ(nlogn)

Any ideas?

Solution

  • I'll give you the broad outline of the proof. You'll have to fill in the details. From this wikipedia article, Stirling's approximation states that for all positive integers n:

    enter image description here

    Using a little algebra to rearrange the terms, we get

    enter image description here

    So n! is bounded above and below by the function

    enter image description here

    Since we're interested in log(n!) we need to determine the behavior of log(f(n)) for large values of n. Doing some more algebra:

    enter image description here

    For large values of n, the first term is much larger than the rest, so

    enter image description here

    which completes the outline of the proof.