Is log(n!) = Θ(n·log(n))?
Solution 1:
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)
Solution 2:
I realize this is a very old question with an accepted answer, but none of these answers actually use the approach suggested by the hint.
It is a pretty simple argument:
n!
(= 1*2*3*...*n) is a product of n
numbers each less than or equal to n
. Therefore it is less than the product of n
numbers all equal to n
; i.e., n^n
.
Half of the numbers -- i.e. n/2
of them -- in the n!
product are greater than or equal to n/2
. Therefore their product is greater than the product of n/2
numbers all equal to n/2
; i.e. (n/2)^(n/2)
.
Take logs throughout to establish the result.
Solution 3:
Sorry, I don't know how to use LaTeX syntax on stackoverflow..
Solution 4:
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.