Is the function \(\lceil \lg n \rceil !\) polynomially bounded? Is the function \(\lceil \lg \lg n \rceil!\) polynomially bounded?
A function \(f(n)\) is polynomially bounded if \(f(n) = O(n^k)\) for some constant \(k\), in other words: if there exists some positive constants \(c\) and \(n_0\) such that:
\[0 \leq \lceil \lg n \rceil ! \leq cn^k \ \forall \ n \geq n_0\]In other words:
\[0 \leq \lg (\lceil \lg n \rceil !) \leq \lg c + k \lg n \ \forall \ n \geq n_0\]So if we can show that \(\lg f(n)) = O(\lg n)\), then we have shown that \(f(n)\) is polynomially bounded.
\[\begin{equation} \begin{split} \lg (\lceil \lg n \rceil !) & = \Theta(\lceil \lg n \rceil \lg( \lceil \lg n \rceil)) \\ & = \Theta(\lg n \lg \lg n ) \\ & = \omega(\lg n) \\ & \neq O(\lg n) \\ \end{split} \end{equation}\]We know from the last exercise that \(\lg n ! = \Theta(n \lg n)\) which lets us set the initial state of the above equation. Next, we perform simplification based on the fact that \(n \leq \lceil n \rceil < n + 1 \ \forall \ n \in \mathbb{R} \implies \lceil \lg n \rceil = \Theta(\lg n)\). Finally, for \(n > 4\), \(\lg n \lg \lg n > \lg n\) which implies that \(\lg (\lceil \lg n \rceil !) \neq O(\lg n)\), therefore \(\lceil \lg n \rceil !\) is not polynomially bounded.
As for \(\lceil \lg \lg n \rceil !\) we can use the same approach:
\[\begin{equation} \begin{split} \lg ( \lceil \lg \lg n \rceil!) & = \Theta(\lceil \lg \lg n \rceil \lg \lceil \lg \lg n \rceil) \\ & = \Theta(\lg \lg n \lg \lg \lg n) \\ & = o(\lg \lg n \lg \lg n) \\ & = o(\lg^2 n) \\ & = o(\lg n) \\ & = O(\lg n) \end{split} \end{equation}\]There is some cleverness behind the transformation of \(\Theta(\lg \lg n \lg \lg \lg n)\) into \(o(\lg \lg n \lg \lg n)\). Suppose \(x = \lg \lg n\), then the transformation looks like: \(\Theta(x \lg x) = o(x^2)\) which is to say that \(x^2\) grows faster than \(x \lg x\) which is plain to see. The final step utilizes the identity \(\lg^bn = o(n^a)\). We therefore conclude that \(\lceil \lg \lg n \rceil !\) is polynomially bounded.