Show that $n! = O(n^{n})$ As the title says, how would you show that $n! = O(n^{n})$? I'm not really understanding how one "shows" the Big O notation of a function mathematically (at least when you're dealing with things that aren't polynomials).


I'm not really understanding how one "shows" the Big O notation of a function mathematically

We say $f(x) = O(g(x))$ as $x \to \infty$ if and only if there is a positive constant $c$ such that, for all sufficiently large values of $x$, $f(x)$ is at most $c|g(x)|$. Symbolically,
$f(x) = O(g(x)) <=> \exists c > 0 \exists x_0 \in \mathbb{R}  : |f(x)| \leq c|g(x)| \ \forall x > x_0$.

So $f(x) = n!$ and $g(x) = n^n$.
If we just choose $c = 1$, we have $n! \leq n^n$ for all $n > x_0 = 0$ where $n$ is an integer. Why? 
Write $n! = 1*2*3*\dots*n$ and $n^n = n*n*n *\dots *n$, where the latter expression has $n$ iterations of $n$. We have $1 \leq n, 2 \leq n, 3 \leq n, \dots, n \leq n$ so therefore $n! \leq n^n$ and $n! = O(n^n)$
