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.