5

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

Euler88 ...
  • 2,090
Dylan Jean
  • 51

5 Answers5

6

HINT:

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

and

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

Mark Viola
  • 179,405
  • Exactly what I was about to suggest. +1 – user217285 Sep 10 '15 at 02:43
  • 1
    @Nitin Thanks! I contemplated referencing Stirling, but it really does not add anything more useful than the crude upper bound (i.e., $n!<n^n$) and might obfuscate if a reader is unfamiliar with Stirling. – Mark Viola Sep 10 '15 at 02:47
4

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?

Victor
  • 3,213
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}$.

Chris Culter
  • 26,806
2

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

Quang Hoang
  • 15,854
0

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

bof
  • 78,265