patternMinor
Is $\lceil\log n\rceil!$ polynomially bounded?
Viewed 0 times
logrceilboundedlceilpolynomially
Problem
Considering the definition, $f(n) = O(n^k)$, for some constant $k$. If I choose $k = 100$ and plot, it shows $n^{100} > \lceil\log n\rceil!$ for all $n > 1$. However, the solutions to Introduction To Algorithms (2009) say that $\lceil\log n\rceil!$ is not polynomially bounded. What's going on?
Solution
Don't trust plots.
By Stirling's approximation (and dropping the ceilings to avoid notational overload),
$$\begin{align*}
(\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\
&= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\
&= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,,
\end{align*}$$
which grows faster than any polynomial. But you're not going to see that by plotting versus $n^{100}$ unless you consider values of $n$ big enough that $\log\log n$ is more than about $99$, i.e., roughly $n\geq e^{e^{99}}\approx 10^{10^{42}}$, and you probably didn't consider values of $n$ quite that big, because no plotting software is going to display values like $(10^{10^{42}})^{100}$.
By Stirling's approximation (and dropping the ceilings to avoid notational overload),
$$\begin{align*}
(\log n)! &\sim \sqrt{2\pi \log n}\left(\frac{\log n}{e}\right)^{\log n}\\
&= \sqrt{2\pi \log n}\, e^{(\log\log n - 1)\log n}\\
&= \sqrt{2\pi \log n}\, n^{\log\log n - 1}\,,
\end{align*}$$
which grows faster than any polynomial. But you're not going to see that by plotting versus $n^{100}$ unless you consider values of $n$ big enough that $\log\log n$ is more than about $99$, i.e., roughly $n\geq e^{e^{99}}\approx 10^{10^{42}}$, and you probably didn't consider values of $n$ quite that big, because no plotting software is going to display values like $(10^{10^{42}})^{100}$.
Context
StackExchange Computer Science Q#110809, answer score: 9
Revisions (0)
No revisions yet.