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 &gt; 0$ there is $n_0 &gt; 0$ such that $0 \leq f(n) &lt; cg(n)$ for all $n &gt; 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 &lt; n^n$ for all $n&gt;2$ (just compare the first two terms of $n!=1\cdot 2\cdot\ldots$ witht those of $n^n=n\cdot n\cdot\ldots$).