# Is $n^n$ is a big-oh n factorial

Is it true or false that $$n^{n} \in \mathcal{O}(n!)$$ ? Any suggestions how to prove/disprove this statement?

• By Stirling, $n^n$ is roughly larger by a factor $e^n$.
– user16034
Mar 20, 2023 at 17:04

$$\frac{n^n}{n!}=\frac{n\cdot n\cdot n\cdots n\cdot n}{n(n-1)(n-2)\cdots 2\cdot 1}=\frac nn\frac{n}{n-1}\frac{n}{n-1}\cdots\frac n2\frac n1>1\cdot1\cdot1\cdots1\cdot n$$ is sufficient.

(In fact, by the same argument the ratio is $$\Omega(n^k)$$ for all $$k$$, and $$n^n\notin O(n^kn!)$$.)

$$\lim_{n \to \infty} \frac{n^n}{n!} = \lim_{n \to \infty} \prod_{i=1}^n \frac{n}{i} \ge \lim_{n \to \infty} \prod_{i=1}^{\lfloor n/2 \rfloor} \frac{n}{i} \ge \lim_{n \to \infty}2^{\lfloor n/2 \rfloor } = +\infty.$$

Exact estimation, from both sides, can be obtain from $$\left(\frac{n}{e} \right)^n< n! < e\left(\frac{n}{2} \right)^n$$ i.e. $$\frac {2^n}{e} \cdot n!

By Stirling's Approximation,

$$n^n = O\left(\frac{n! \cdot e^n}{\sqrt{n}}\right)$$

$$\lim_{n \to \infty} \frac{e^n}{\sqrt{n}} = \infty$$

Meaning that $$n^n$$ isn't $$O(n!)$$, however you do have that $$n!$$ is $$O(n^n)$$.

$$n! = 1 \cdot 2 \cdot 3 ... \cdot n ≤ 1 \cdot n \cdot n ... \cdot n = n^{n-1} = n^n / n$$. Or $$n^n ≥ n \cdot n!$$. So clearly not O (n!).