3
$\begingroup$

I'm trying to proof/refute the following equation:

$$n^n = \Omega(n!)$$

Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem.

$$\lim_{n\to \inf}{{f(n)}\over{g(n)}} = K$$

However, in this case $n!$ is somewhat of a party-stopper. I found Stirling's approximation which states that:

$$n! \approx \left(\frac{n}{e}\right)^n\sqrt{2πn} $$

My idea was therefore:

$${n^n}\over{(\frac{n}{e})^n\sqrt{2πn}}$$ $${n^n}\over{\frac{n^n}{e^n}\sqrt{2πn}}$$ $${e^n}\over{\sqrt{2πn}}$$ $$\lim_{x\to \infty}{{e^2n}\over{2πn}} = \infty$$

$$ 0 < K \leq \infty $$

therefore the original equation is true.

Is that approach "ok", did I understand Stirling's approximation correctly?

$\endgroup$
  • 6
    $\begingroup$ You don't need Stirling here. You could simply use the definition of $n!$ to prove that $n^n \ge n \cdot n!$. $\endgroup$ – Jukka Suomela May 11 '14 at 9:24
  • 2
    $\begingroup$ What you actually show is $n^n = \omega(n!)$. $\endgroup$ – Yuval Filmus May 11 '14 at 13:30
4
$\begingroup$

Stirling's approximation states that $$ n! \sim \sqrt{2\pi n} (n/e)^n. $$ This notation means that the ratio between the two sides tends to 1 as $n$ tends to infinity. For your purposes, we can simply write $$ n! = \Theta(\sqrt{n} (n/e)^n). $$ Since $\sqrt{n} = o(e^n)$, $$ n! = o(n^n). $$

If all you want to show $n! = O(n^n)$, then as Jukka mentions you can use the simple bound $n! \leq n^n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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