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$
2
  • 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$ May 11, 2014 at 9:24
  • 2
    $\begingroup$ What you actually show is $n^n = \omega(n!)$. $\endgroup$ May 11, 2014 at 13:30

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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