In this writeup we shall prove:
log(n!) = Θ(n log n)
To prove that something is f(x) = Θ(g(x)), it is sufficient to show that:
f(x) = Ω(g(x)) and...
f(x) = O(g(x))
Recall that n! = n × (n-1) × (n-2) × (n-3) ... × 2 × 1
Thus:
log(n!) <= log(n^n)
log(n!) <= n log(n) therefore:
log(n!) = Θ(n log n)
Also:
log(n!) >= log( (n/2)^(n/2) )
log(n!) >= n/2 log(n/2)
log(n!) >= n ( log(n) - log(2) ) / 2 Therefore...
log(n!) = Ω(n log n)
see also: Striling's Formula, big-oh notation, Properties of Logarithmic Functions.