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

We will use the following facts in this proof:

1. $\lg n! = \Theta(n \lg n)$ (eqn. (3.18) see Exercise 3.2-3)
2. $\lceil n \rceil = \Theta(n)$ because $\lceil n \rceil \ge n$ for any $n$ and $% $ for all $n \ge 1$

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$. Hence, $\lg (f(n)) \le ck \lg n$, i.e. if a function is polynomially bounded, then $\lg (f(n)) = O(\lg n)$ and vice versa.

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

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:

The last line comes from the fact that, $\lg^b n = o(n^a)$, i.e. logarithmic functions are polynomially bounded.

Hence, 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.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.