I'm totally lost so please be really explicit in your answers. Thanks for the help.

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$

  • $\begingroup$ I think $c=a=1$ is enough. $\endgroup$
    – Pedro Tamaroff
    May 5 '13 at 19:59
  • 3
    $\begingroup$ Have you considered Stirling's formula for estimating the factorial? $\endgroup$ May 5 '13 at 19:59
  • $\begingroup$ @MarkBennet I did, but that got me nowhere. I ended up with a really messy inequality, and I had no idea how to proceed. $\endgroup$
    – 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).

  • $\begingroup$ How does proving $\frac{f(n^2)}{f(n)}$ grows faster than $\frac{g(n^2)}{g(n)}$ prove the function is polynomially bounded? $\endgroup$
    – sdf
    May 6 '13 at 2:40
  • $\begingroup$ @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$. $\endgroup$ May 6 '13 at 13:48
  • 1
    $\begingroup$ @BrianM.Scott Oops, yeah your right. I mixed them up. Regardless, how does this show that $f(n)$ is polynomially bounded? $\endgroup$
    – sdf
    May 6 '13 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.