Possible explanation for why lg(n!)=O(nlg(n))

Question

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)

Answer 1

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

Answer 2

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.

Answer 3

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

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

Answer 4

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.