Proof based on definition of big-$O$

Question

I want to prove that $n! = O(n^n)$ based on the definition of big-$O$.

---

I find it pretty easy to show that $n! = O(n^n)$ by simply showing that $n (n-1) < n \cdot n \ldots$ etc. However I can't figure out how to prove this based on the definition of big-$O$. How can I prove this based upon the definition?

Answer 1

We have $\displaystyle \lim_{n \to \infty} \frac{n!}{n^n}=0, $ which shows that $n!=o(n^n)$ and hence $n!=O(n^n)$.

To compute the limit one can make use of Stirling's formula:
$$n!\sim \sqrt{2\pi n} \frac{n^n}{e^n}.$$

Answer 2

For $n>0$ let $f(n)=n!/n^n$.Then $f(n+1)=f(n)\cdot (n/(n+1))^n<f(n)$ so $f(n)\leq f(1)=1$ so $n!\leq n^n$.

DEF'N: $g(n)=O(h(n)$ as $n\to \infty$ iff $\exists k>0 \;\exists n_0\;(n>n_0\implies |g(n)|\leq k|h(n)|).$

Here we can let $g(n)=n!, h(n)=n^n, n_0=1,$ and $k=1.$