Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

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?

share|cite|improve this question

marked as duplicate by Michael Hoppe, Lost1, Yiorgos S. Smyrlis, TMM, Your Ad Here Feb 12 '14 at 21:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Your professor is basing his assertion on what? Does he have an explanation? That's what I would ask if I were in his class. – imranfat Feb 12 '14 at 16:54
I asked once, and he referred to Stirlings approximation, which he simplified as something like n^(1/2) * n^n. – beachwood23 Feb 12 '14 at 16:55
There's an $e^{-n}$ missing in that version of Stirling. – Daniel Fischer Feb 12 '14 at 16:56
Ah. That would certainly inhibit the growth! Glad to know I'm not going insane. – beachwood23 Feb 12 '14 at 16:57
See this question that shows $lim_{n\rightarrow \infty} \frac{n1}{n^n} = 0$ so $n^n$ grows faster. – John Habert Feb 12 '14 at 16:59
up vote 6 down vote accepted

"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.

share|cite|improve this answer
Although n^n > n! does not prove that n!/n^n -> 0 BUT it does prove that n^n/n! -/> 0. That is, it doesn't prove that it's a higher order of growth, but it proves that it's order of growth is at least as high. This is contrary to his professors claims. – Cruncher Feb 12 '14 at 18:21

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.)

share|cite|improve this answer
Why the downvote? – Thomas Feb 12 '14 at 16:56
This is definitely not a proof, not even very convincing: there are quite a huge number of sequences growing very slowly for the first $K$ terms, and yet very fast afterwards... – Clement C. Feb 12 '14 at 16:56
He didn't mispeak. He literally just corrected a student, and expanded on it in a previous lecture. He's a smart guy, I'm going to assume its a simple mixup. – beachwood23 Feb 12 '14 at 16:56
@PLKTU: What is the "correct explanation" then? I don't see you trying to provide one. – Thomas Feb 12 '14 at 17:09
I did not say the answer was wrong — I merely said that th evidence you give is not a proof (on which you agree) not even evidence at all — since it can be discarded easily by other examples of sequence with the same first terms. Phrased differently, my point is that your answer is not bringing much insight. – Clement C. Feb 12 '14 at 17:29

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!$

share|cite|improve this answer
This is definitely the right idea. The two functions are equal for $n=1$ and $n!$ never catches up afterwards. – Patrick Feb 12 '14 at 17:20
@Patrick Yes, just like the sequences $n-(n-1)/2^n$ and $n$, and yet... – Did Feb 12 '14 at 17:36
@Did Ok, so I am incorrectly taking "Higher order of growth" = "Higher rate of growth" – Patrick Feb 12 '14 at 17:40

Your professor is wrong, and the explanation can be found here on page 5.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.