Take the 2-minute tour ×

Possible Duplicate:
Is log(n!) = Θ(n·log(n))?

My "proof" for why lg(n!) is O(nlg(n)) is because n is polynomially larger than lg(n!), so therefore nlg(n) would always be polynomially larger than lg(n!). Is that an acceptable reason? or do you have to mathematically prove it (in which case I would not know how to deal with the factorial)

share|improve this question
add comment

marked as duplicate by Mysticial, Daniel Fischer, Cody Gray, Gilles, Joe Feb 1 '12 at 20:47


4 Answers

The usual proof I've seen is that for sufficiently large n, n! < nn. Take the logarithm of both sides to get log(n!) < log(nn). Since log(ba) = a log(b), we get log(n!) < n log(n).

share|improve this answer
n^n is greater than n! :) –  Chris Nash Feb 1 '12 at 1:26
@ChrisNash: Yes, I accidentally had my inequalities backwards. Already fixed :) –  hammar Feb 1 '12 at 1:28
add comment

You probably do need something a bit more mathematically strict, but it's not too difficult. Since

 lg(n!) = lg 1 + lg 2 + lg 3 + ..... + lg n

you might consider the area under the graph of y = lg x and approximate it with the http://en.wikipedia.org/wiki/Rectangle_method . You'll get something like http://en.wikipedia.org/wiki/Stirling's_approximation .

Because it's 'little o' your rectangles need to bound above and below.

share|improve this answer
add comment

Use stirling's approximation: http://en.wikipedia.org/wiki/Stirling%27s_approximation

ln n! = n\ln n - n +O(ln(n)) 
share|improve this answer
add comment

Recall that ln(a⋅b) = ln(a) + ln(b). Therefore, ln(n!) = ln(n⋅(n−1)⋅…⋅2⋅1) = ln(n) + ln(n−1) + … ln(2) + ln(1); this yields n⋅ln(n) ≤ ln(n!) by inspection.

share|improve this answer
add comment
