## Tuesday, June 5, 2012

### Better upper bound for factorial?

Tonight I was puzzled by the question, if an algorithm $$\Pi$$ has running time $$O(n!)$$, does $$\Pi$$ belong to EXPTIME? To rehash, EXPTIME contains all algorithms that has running time $$O(2^{n^k})$$. For brevity, I use the notation $$f(x) \prec g(x)$$ to denote that $$f(x)$$ grows slower than $$g(x)$$. We know that $$2^n \prec n! \prec n^n$$ but I don't think I can show that $$n^n$$ belongs to EXPTIME. I need a tighter bound.

It turns out that $$n! \prec 2^{n^2}$$.

Proof.
• The growth of $$n!$$ is $$\frac{(n+1)!}{n!} = n+1$$.
• The growth of $$2^{n^2} = (2^n)^n$$ is $\begin{eqnarray} \frac{(2^{n+1})^{n+1}}{(2^n)^n} & = & \frac{(2 \cdot 2^n)^{n+1}}{(2^n)^n} \\ & = & \frac{(2 \cdot 2^n)^n \cdot (2 \cdot 2^n)}{(2^n)^n} \\ & = & \frac{2^n \cdot \cancel{(2^n)^n} \cdot (2 \cdot 2^n)}{\cancel{(2^n)^n}} \\ & = & 2 \cdot 2^{2n} = 2^{2n+1} \\ \end{eqnarray}$
Since $$n+1 < 2^{2n+1}$$ for all $$n$$, therefore $$n! \prec 2^{n^2}$$.
$$\Box$$
So it turns out that an $$O(n!)$$ algorithm belongs to the class $$O(2^{n^k})$$ where $$k = 2$$, so such algorithm indeed belongs to EXPTIME.

Update (June 7, 2012): it turns out that showing $$n^n$$ belongs to EXPTIME isn't that hard.

The growth of $$n^n$$ is $\begin{eqnarray} \frac{(n+1)^{n+1}}{n^n} & = & \frac{(n+1)^n (n+1)}{n^n} \\ & = & \left( \frac{n+1}{n} \right)^n (n+1) \\ & = & \left( 1 + \frac{1}{n} \right)^n (n + 1) \\ & \approx & (n+1)e \\ \end{eqnarray}$

And that's because $$\lim_{n \to \infty} \left( 1 + \frac{1}{n} \right)^n = e$$.  So $$n^n$$ even grows slower than $$2^{n^2}$$.