Question

Why is this true? How do factorials compare to logarithms? log(n!) = Θ(n log n)

Answer 1

Show `log(n!) in O(n log(n))` then show `log(n!) in Theta(n log(n))`

Explanation:

`color(white)()`
`bb (log(n!) in O(n log(n)))`

For `n >= 1`, `n!` has `n` terms, each `<= n`

So `n! <= n^n`, so `log(n!) <= log(n^n) = n log(n)`

Therefore `log(n!) in O(n log(n))`

`color(white)()`
`bb (log(n!) in Theta(n log(n)))`

To prove the stronger result `n! in Theta(n log(n))`, proceed as follows:

We need to find `N in ZZ` and `c > 0` such that

`log(n!) >= c(n log(n)) AA n >= N`

Let `n >= 10`.

Let `k = floor(n / 2)`

Consider `n!`

`n! = k! ((n!) / (k!))`

`(n!) / (k!) = prod_(i=k+1)^(n) i > prod_(i=k+1)^(n) (k+1) = (k+1)^(n-k)`

Also, since `k >= 5`, we find (proof left to reader):

`k! > 2^(k+1) >= 2^(n-k)`

So:

`n! = k! ((n!) / (k!)) > 2^(n-k) * (k+1)^(n-k) = (2(k+1))^(n-k)`

`>= n^(n-k) >= n^(n/2)`

So: `log(n!) > log(n^(n/2)) = 1/2 (n log(n))`

So `N=10` and `c = 1/2` work.

Hence `log(n!) in Theta(n log(n))`