6
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.