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