Approximating (log n)!

Question

I understand approximating log n! is (n * log n) by Stirling's formula. But, How about (log n)! ? I cannot think about how to approximate (log n)! Because it is log multiply. How can we get its approximate value?

Answer 1

By Stirling's approximation, we have the following asymptote.

$$n! \sim \sqrt{2\pi} \sqrt{n}\ n^n e^{-n}$$

Let us ignore the constant $\sqrt{2\pi}$ (but don't forget it goes in front of all of these) and insert $\log n$ in place of $n$.

$$\sqrt{\log n}\ (\log n)^{\log n} e^{-\log n}$$

We may simplify: $e^{-\log n} = n^{-1}$ by log/exponent rules, and we also $a^{\log b} = b^{\log a}$ in general, so $(\log n)^{\log n} = n^{\log \log n}$. Replacing these in the above expression, we obtain the following.

$$\sqrt{\log n}\ n^{\log \log n} n^{-1}$$

We can combine the exponents into one, if we feel like it.

$$\sqrt{\log n}\ n^{-1 + \log \log n}$$

The exponent $-1 + \log \log n$ diverges to infinity, but it does so incredibly slowly. Indeed, $-1 + \log \log n > 1$ only when $n > e^{e^2} \approx 1600$. The function above, therefore, grows faster (in terms of big-O) than every polynomial $n^k$ for any constant $k$. However, it is dominated by the exponential functions, $e^{an}$ for any constant $a > 0$.

Indeed, if you take the logarithm of the above expression and ignore the lower order terms, you get $(\log \log n)(\log n)$. This is beat (in terms of big-O) by $n^p$ for any real $p \in (0,1)$. So $(\log n)! \in \mathcal{O}(e^{n^p})$ for any constant $p \in (0,1)$.