log(n!) = Theta(nlogn)

Question

How to explain this equation?  It seems to be clear that log(n!) = O(n log n), since log (1.2.3.4.5....n) <= log (n.n.n.n...n)    (n times).

However, how do we prove that log (n!) = Omega (n log n)

Answer 1

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)
                                        = n/2 * log(n/2)