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

Polynomially Bounded: $f(x)$ is polynomially bounded if for some constants $c$, $a$ and $x_0$, $$f(x) \le cx^a$$, for all $x > x_0$

• I think $c=a=1$ is enough. May 5 '13 at 19:59
• Have you considered Stirling's formula for estimating the factorial? May 5 '13 at 19:59
• @MarkBennet I did, but that got me nowhere. I ended up with a really messy inequality, and I had no idea how to proceed.
– sdf
May 5 '13 at 20:00

Note that $$f(n^2)=\lceil\lg\lg( n^2)\rceil!=\lceil\lg(2\lg n)\rceil!=\lceil1+\lg\lg n\rceil!=(1+\lg\lg n)\cdot f(n),$$ that is $\frac{f(n^2)}{f(n)}$ grows slower than $n$. On the other hand, with $g(n) = c n^a$, we have $\frac{g(n^2)}{g(n)}=n^a$, so this suggests that $a=1$ should suffice (or in fact any $a>0$). (To make this stringent, note that $f$ is monotonic).
• How does proving $\frac{f(n^2)}{f(n)}$ grows faster than $\frac{g(n^2)}{g(n)}$ prove the function is polynomially bounded?
• @sdf: That isn’t what Hagen did. He showed that $\frac{f(n^2)}{f(n)}$ grows slower than $\frac{g(n^2)}{g(n)}$ if $g(n)=cn$. May 6 '13 at 13:48
• @BrianM.Scott Oops, yeah your right. I mixed them up. Regardless, how does this show that $f(n)$ is polynomially bounded?