In our algorithms class, my professor insists that n! has a higher order of growth than n^n. This doesn't make sense to me, when I work through what each expression means.
n! = n * (n-1) * (n-2) * ... * 2 * 1
n^n = n * n * n * n * ... * n * n
Since n is, by definition, greater than n -1 or n-2, shouldn't any n^n, which is the product of n number of n's, be greater than n!, which is the product of an n number of integers less than n?
On
You are right that $n^n$ grows faster than $n!$. You can see this question with answer (thanks to @JohnHabert for his comment above) for a proof which says exactly what you are saying. This is illustrated by just considering the first couple of numbers $$ \begin{align} 1^1 = 1 \quad &\quad\quad 1! = 1\\ 2^2 = 4 \quad &\quad\quad 2! = 2\\ 3^3 = 27 \quad &\quad\quad 3! = 6\\ 4^4 = 256 \quad &\quad\quad 4! = 24 \\ 5^5 = 3125 \quad &\quad\quad 5! = 120 \\ \end{align} $$ (Your professor might just have misspoken. I would go ask him for clarification.)
On
If $n\in \mathbb{N}$, Then $n! = 1 \times 2 \times 3\times 4...............\times (n-2)\times (n-1)\times n$
Now $n\geq n$ and $n>(n-1)$ and $n>(n-2)$ and $n>(n-3)$......... $n>4\;\;,n>3\;\;,n>2\;\;,n>1$
So $n\cdot n\cdot n\cdot ............\cdot n(n-\bf{times})\geq n\cdot (n-1)\cdot (n-2)....3\cdot 2 \cdot 1$
So $n^n\geq n!$
"Higher order of growth" does not mean that $n!\lt n^n$ but the stronger property that $$n!/n^n\to0.$$ To prove that this property holds, note that $n\geqslant2k$ for every $1\leqslant k\leqslant n/2$ and $n\geqslant k$ for every $n/2\lt k\leqslant n$, hence $$ n^n=\prod_{k=1}^{n}n\geqslant\prod_{1\leqslant k\leqslant n/2}(2k)\cdot\prod_{n/2\lt k\leqslant n}k=2^{n/2}\cdot n!, $$ which proves that $$ \frac{n!}{n^n}\leqslant\frac1{2^{n/2}}\to0. $$ Thus, indeed $n^n$ has a higher order of growth than $n!$, not the opposite.