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