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

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

## No comments:

Post a Comment