0
$\begingroup$

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

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

5 Answers 5

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.