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

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.

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

• One warning, one comment: Big-O does not stay intact after taking the logarithm if your values are close to 1. And many times f(n) is not O(g(n)) but log f(n)) = O(log(g(n))). For example if f(n) is between k-th root and k-th power of g(n). In this case here everything is fine. Commented Aug 13 at 22:11

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}

• That's right. Or simply $n!<n^n$. But then you don't know if it is tight. Commented Aug 14 at 11:35
• You can lower bound the first $n/2$ terms by $\log n/2$ to get tightness
– SamM
Commented Aug 14 at 14:56

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