Is log(n!) = Θ(n·log(n))?

Question

I am to show that log(n!) = Θ(n·log(n)).

A hint was given that I should show the upper bound with nⁿ and show the lower bound with (n/2)^(n/2). This does not seem all that intuitive to me. Why would that be the case? I can definitely see how to convert nⁿ to n·log(n) (i.e. log both sides of an equation), but that's kind of working backwards.

What would be the correct approach to tackle this problem? Should I draw the recursion tree? There is nothing recursive about this, so that doesn't seem like a likely approach..

user_248349 · Answer

Remember that

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)

You can get the upper bound by

log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n)
                                = n*log(n)

And you can get the lower bound by doing a similar thing after throwing away the first half of the sum:

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n) 
                                       = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                       >= log(n/2) + ... + log(n/2)
                                        = n/2 * log(n/2)

dsimcha_23903 · Answer

See Stirling's Approximation:

ln(n!) = n*ln(n) - n + O(ln(n))

where the last 2 terms are less significant than the first one.

user_252704 · Answer

Helping you further, where Mick Sharpe left you:

It's deriveration is quite simple: see http://en.wikipedia.org/wiki/Logarithm -> Group Theory

log(n!) = log(n * (n-1) * (n-2) * ... * 2 * 1) = log(n) + log(n-1) + ... + log(2) + log(1)

Think of n as infinitly big. What is infinite minus one? or minus two? etc.

log(inf) + log(inf) + log(inf) + ... = inf * log(inf)

And then think of inf as n.

user_206328 · Answer

This might help:

e^ln(x) = x

and

(l^m)ⁿ = l^m*n

user_865714 · Answer

If you reframe the problem, you can solve this with calculus! This method was originally shown to me via Arthur Breitman https://twitter.com/ArthurB/status/1436023017725964290.

First, you take the integral of log(x) from 1 to n it is n*log(n) -n +1. This proves a tight upper bound since log is monotonic and for every point n, the integral from n to n+1 of log(n) > log(n) * 1. You can similarly craft the lower bound using log(x-1), as for every point n, 1*log(n) > the integral from x=n-1 to n of log(x). The integral of log(x) from 0 to n-1 is (n-1)*(log(n-1) -1), or n log(n-1) -n -log(n-1)+1.

These are very tight bounds!

Is log(n!) = Θ(n·log(n))?

10 Answers