Prove that $n! = O(n^n)$

Question

I thought $n^n$ was greater than $n!$. How would I go about proving this?

I have this so far:

Assume that $P$($n$) is true $n!$ = O($n^n$)

Assume that $P$($n+1$) is also true $(n+1)! = O((n+1)^{n+1})$

Answer 1

You are correct, $n^n$ does grow faster than $n!$ -- hence $n!$ is $O(n^n)$.

However, induction doesn't make sense here. You are confused by the notation -- "big O" statements don't involve numbers n, it is a statement on functions, $f(n) = n!$ and $g(n) = n^n$.

Try writing out $n^n$ and $n!$ in terms of products. $n! = n * (n-1) * ... * 1$. Compare this to the product expression of $n^n$.