# Is $\lceil\log n\rceil!$ polynomially bounded?

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?

## 2 Answers

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}$$.

Let's choose $$n=2^k$$, and see if $$T(n)=\lceil\log_2 n \rceil !$$ is bounded by a "polynomial of $$2^k$$" i.e. is $$O(2^{mk})$$ for some constant $$m$$. That is, $$O({(2^m)}^k)$$ for some $$m$$, or equivalently $$O(b^k)$$ for some basis $$b>1$$. In other words, we want to check if $$T(n)=T(2^k)$$ is bounded by some exponential of $$k$$.

We have $$T(2^k) = \lceil\log_2 2^k \rceil ! = \lceil k \rceil ! = k !$$ However $$k!$$ grows faster than any exponential. Hence, $$T(n)$$ is not polynomially bounded w.r.t. $$n$$.