# 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.