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