# Prove $n! = o(n^n)$ without limits

I've already proven the statement using the limit definition of $$o(g(n))$$ and Stirling's approximation, but how do I prove it using the main definition for $$o$$ notation provided in CLRS instead?

Definition: $$f(n) = o(g(n))$$ if for all $$c > 0$$ there is $$n_0 > 0$$ such that $$0 \leq f(n) < cg(n)$$ for all $$n > n_0$$.

I've tried substituting Stirling's approximation again, but I am unaware of any analytic means of determining $$n_0$$ as a function of $$c$$ due to the presence of the $$n$$ term as both a base and exponent in the resulting inequality.

## 1 Answer

You do not need anything as fancy as Stirling. It is easy to see that $$n!\cdot n < n^n$$ for all $$n>2$$ (just compare the first two terms of $$n!=1\cdot 2\cdot\ldots$$ witht those of $$n^n=n\cdot n\cdot\ldots$$).

• I missed completely that he asked the trivial question. Proving how n! is related to n^n e^-n, that would be a lot more tricky. – gnasher729 Sep 28 '20 at 10:12
• Prove that n! = o (n^n 2^-n): Split the product into the numbers 1 to n/8, n/8 to 2n/8, 2n/8 to 3n/8 etc. – gnasher729 Sep 28 '20 at 10:22
• I know it's easy to see that n! < n^n for all n > 2. My question wasn't what the general intuition behind the claim was. I was wondering how you would prove the claim formally using the definition I provided in my question. What would your choice of n_0 be for every choice of c? If c = 0.0001 for instance, then you can't say n! < cn^n simply "for all n>2". – kotu Sep 28 '20 at 15:39
• @kotu I do not want to give a detailed exposition because I don't want to accidentally do someone's homework. If you let $n_0 > 1/c$ you just need to use elementary algebra on the expression $n!\cdot n <n^n$ to derive that $n!<cn^n$. – Tom van der Zanden Sep 29 '20 at 9:12
• @kotu I just needed any kind of separation between the functions. That $n!\cdot n < n^n$ occured to me after comparing the expansion of $n!$ and $n^n$ and it was the simplest inequality you can easily prove from comparing the expansions. To see that $n>1/c$ observe that $n^n$ is bigger than $n!$ by (at least) a factor of $n$. So, if we have a very small $c$ in front of $n^n$ - making it smaller by a factor $1/c$, we need to make it bigger by $1/c$ again by assuming $n>1/c$. It is essentially just the same as proving $n=o(n^2)$. – Tom van der Zanden Sep 29 '20 at 20:44