Prove log(n!) ∈ Θ(n log(n)).

Here log() is log() base anything, and lg() is log() base 2.

a. Prove log(n!) ∈ Ο(n log(n)).

b. Prove log(n!) ∈ Ω(n log(n)).

To prove a:
log(n!) = log(n*(n-1)*(n-2)* ... *2*1) = log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1) <= log(n) + log(n) + log(n) + ... + log(n) + log(n) = n log(n)
Therefore log(n!) <= n log(n) where c = 1, or log(n!) ∈ Ο(n log(n)).

To prove b:
log(n!) = log(n*(n-1)*(n-2)* ... *2*1) = log(n) + log(n-1) + log(n-2) + ... + log(2) + log(1) >= log(n) + log(n-1) + log(n-2) + ... + log(n-(⌈n/2⌉-1))
In the last summation we have ⌈n/2⌉ terms. As an example, list the terms for n=6 and n=7, and make sure in both cases we have ⌈n/2⌉ terms.
Replace each of the ⌈n/2⌉ terms with the smaller value of log(n/2). We get:
log(n) + log(n-1) + log(n-2) + ... + log(n-(⌈n/2⌉-1)) >= log(n/2) + log(n/2) + log(n/2) + ... + log(n/2)
because log(n) > log(n/2) and log(n-1) > log(n/2) and so on including log(n-(⌈n/2⌉-1)) > log(n/2).
All these relations are easy to see except the last one. To see log(n-(⌈n/2⌉-1)) > log(n/2), note log() is a continuous and increasing function and answer
is n-(⌈n/2⌉-1) > n/2?
Or is n-⌈n/2⌉+1 > n/2?
Or is n+1-n/2 > ⌈n/2⌉?
Or is n/2+1 > ⌈n/2⌉? YES!
Now, since we have ⌈n/2⌉ terms,
log(n) + log(n-1) + log(n-2) + ... + log(n-(⌈n/2⌉-1)) >= log(n/2) + log(n/2) + log(n/2) + ... + log(n/2) = ⌈n/2⌉ log(n/2) >= n/2 log(n/2) >= n/2 log(n)/2
To see the last >= relation, answer
is lg(n/2) >= lg(n)/2?
Or is lg(n) - lg(2) >= lg(n)/2?
Or is lg(n) - 1 >= lg(n)/2?
Or is 2lg(n) - 2 >= lg(n)? YES, for n >= 4.
So, finally we have log(n!) >= 1/4 n log(n) where c = 1/4. Therefore log(n!) ∈ Ω(n log(n)).