# 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.

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