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)).