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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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!<n^n<e^n \cdot n!$$

Answer 4

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

Answer 5

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