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

Question

1416 views around the world

You can reuse this answer
Creative Commons License

Answer 1 · 2015-09-13T23:08:00

Show $log (n!) \in O (n log (n))$ $log(n!) in O(n log(n))$ then show $log(n!) in Theta(n log(n))$

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