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

1 Answer
Sep 13, 2015

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