Is the function $$\lceil\lg n\rceil!$$ polynomially bounded? Is the function $$\lceil\lg \lg n\rceil!$$ polynomially bounded?

If a function $$f(n)$$ is polynomially bounded then there exist constants $$c, k, n_0$$ such that for all $$n \ge n_0$$, $$f(n) \le cn^k$$. this means,

$\lg (f(n)) \le ck \lg n \iff \lg(f(n)) = O(\lg n)$

Also make note of the following facts that we will use in our derivation:

1. $$\lg n! = \Theta(n \lg n)$$ (see previous exercise)

2. $$\lceil n \rceil = \Theta(n)$$ because $$n \leq \lceil n \rceil \leq 2n$$ for all $$n \ge 1$$

We can analyze $$\lceil\lg n\rceil!$$ as follows:

\begin {aligned} \lg\left(\lceil\lg n\rceil!\right) & = \Theta(\lceil\lg n\rceil \lg \lceil\lg n\rceil) \\ & = \Theta(\lg n \lg \lg n) \\ & = \omega(\lg n) \end {aligned}

The last line comes from the fact that, for $$n > 4$$, $$\lg n \lg \lg n > \lg n$$. Hence, asymptotically $$\lg\left(\lceil\lg n\rceil!\right)$$ is definitely larger than $$\lg n$$.

In other words, $$\lg\left(\lceil\lg n\rceil!\right) \ne O(\lg n)$$, i.e. $$\lceil\lg n\rceil!$$ is not polynomially bounded.

We can analyze $$\lceil\lg \lg n\rceil!$$ as follows:

\begin {aligned} \lg\left(\lceil\lg \lg n\rceil!\right) & = \Theta(\lceil\lg \lg n\rceil \lg \lceil\lg \lg n\rceil) \\ & = \Theta(\lg \lg n \cdot \lg \lg \lg n) \\ & = o(\lg \lg n \cdot \lg \lg n) \\ & = o((\lg \lg n)^2) \\ & = o(\lg^2 \lg n) \\ & = o(\lg n) \\ & = O(\lg n) \\ \end {aligned}

The last line comes from the fact that, $$\lg^b n = o(n^a)$$, i.e. polylogarithmic functions grows slower than polynomial functions. In this case, $$a = 1$$ and $$b = 2$$.

This derivation shows that, asymptotically $$\lg\left(\lceil\lg \lg n\rceil!\right)$$ is definitely smaller than $$\lg n$$. In other words, $$\lg\left(\lceil\lg \lg n\rceil!\right) = O(\lg n)$$, i.e. $$\lceil\lg \lg n\rceil!$$ is polynomially bounded.