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.

Log in or registerto write something here or to contact authors.