patternMinor
Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation
Viewed 0 times
theomegaapproximationwithhelprefutestirlingproof
Problem
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?
$$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?
Solution
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$.
$$ 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$.
Context
StackExchange Computer Science Q#24597, answer score: 4
Revisions (0)
No revisions yet.