How to simplify $O(\log (n!))$?

Question

I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any exponential $a^n$, so for sure $O(\log (n!))$ is at least $O(\log(a^n))=O(n\log a)= O(n)$. I also know that it is smaller than $n^n$, so $O(\log(n!))$ is at most $O(\log(n^n)))=O(n\log n)$. But is it one of the two bounds I found? Or is it something in the middle? I would like to simplify the asymptotic time complexity I wrote at the beginning, and I wonder if we know precisely what $O(\log(n!))$ is.

Answer 1

You can solve it using Stirling's Formula.

From Stirling's formula we know that $$n!=O\left(\sqrt{2\pi n} \left( \frac{n}{e} \right)^n \right) \ ,$$

so, passing to logarithm, we have: $$\log(n!) = O\left(\log \left( \sqrt{2\pi n} \left( \frac{n}{e} \right)^n \right) \right) = O(\log n) + O(n (\log n-\log e) = O(n\log n) \ .$$

So, at the end, your time complexity reduces to $O(n\log n)$.

Answer 2

It is rather straightforward to show $\log(n!) = O(n\log n)$ without using Stirling's approximation or any integration:

\begin{align} \log(n!) &= \log (n\times (n-1) \times\cdots\times 2 \times 1) \\ &= \log(n) + \log(n-1) + \cdots+ \log(2) + \log(1) \\ &\le \log(n) + \log(n) + \cdots+ \log(n) + \log(n) \\ &= n\log n . \end{align}

Answer 3

Without knowing Stirling,

$$\log(n!)=\sum_{k=1}^n \log(k).$$

We can replace the sum by an integral because for $t\in[k,k+1]$, $\log(k)\le\log(t)$ and

$$\sum_{k=1}^n \log(k)<\int_{t=1}^{n+1}\log(t)\,dt=(t\log(t)-t)\bigg|_1^{n+1}=(n+1)\log(n+1)+1$$ which is $O(n\log(n))$.