Which function grows at a faster rate? $n!$ or $2^{n^2}$

Question

I have two functions:

$n!$

$2^{n^{2}}$

What is the difference between the growth of these two? My thought is that $2^{n^2}$ grows much faster than $n!$.

Answer 1

We know $2^{n}$ grows much faster than $n$, so $$2^{n^2}>2^{1+2+\cdots+n}$$ grows much faster than $$n!=1\cdot 2\cdots n.$$

Answer 2

Create a sequence $\{a_n\} = \frac{2^{n^2}}{n!}$ and let $n$ get infinitely large. Upon using the ratio test: $$ \frac {a_{n}}{ a_{n-1}}=\frac{2^{n^2}/n!}{2^{(n-1)^2}/(n-1)!}=\frac{2^{n^2}}{n2^{(n-1)^2}}=\frac{2^{2n-1}}{n}. $$

What can one say about this?

Answer 3

HINT:

$$\log 2^{n^2}=n^2\log 2$$

and

$$\log n!<n\log n$$

Answer 4

There's a nice combinatorial relationship between the two: $n!$ is the number of $n\times n$ permutation matrices, and $2^{n^2}$ is the number of $n\times n$ binary matrices. Every permutation matrix is a binary matrix, so we immediately have $2^{n^2}\geq n!$.

Moreover, the probability that a random binary matrix is a permutation matrix is intuitively very small. Concretely, for each permutation matrix, we can form $2^{(n^2-n)/2}$ unique binary matrices by filling in the remaining spots to the right of the given 1s. So $2^{n^2}\geq n!2^{(n^2-n)/2}$.

Answer 5

$$\frac{2^{n^2}}{n!}=\frac{2^n}1\cdot\frac{2^n}2\cdot\frac{2^n}3\cdot\cdots\cdot\frac{2^n}n\rightarrow\infty$$