Exercise 3.2.4

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

If we take the definition of polynomially bound:

$$ f(n) \leq cn^k $$

and take the logarithm of each side, we get:

$$ \lg{f(n)} \leq \lg{c} + k\lg{n} $$

Thus, a function is polynomially bound if $\lg{f(n)} = \Theta(\lg{n})$.

If we let $m = \lceil \lg{n} \rceil$, from the previous exercise we know that:

$$ \lg{m!} = \Theta(m\lg{m}) = \Theta(\lceil\lg{n}\rceil\lg\lceil\lg{n}\rceil) $$

Thus, it is not polynomially bounded. As for the other, if le let $p = \lceil \lg\lg{n} \rceil$:

$$ \begin{aligned} \lg{p!} &= \Theta(p\lg{p}) = \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\lg{n}) = o(\lg{n}) \end{aligned} $$

The last follows from the statement in the chapter that polylogarithmic functions grow slower than polynomial functions.