I know this question has been answered before, but I didn't understand the answers and my reputation is too low to comment, since I'm new to stack exchange.

Polynomially bounded (I'm pretty sure) means that for function $f(x)$, there is a polynomial function $g(x)$ for which $g(x) \le f(x)$ for all values of x above 0, and there is a polynomial function $h(x)$ for which $f(x) \le h(x)$ for all values of x above 0.

People give $2^x$ as an example of a function that is not polynomially bounded, but isn't $(2^x)-1$ smaller in all cases and $(2^x)+1$ greater in all cases?


  • $\begingroup$ You should link to the questions you're referring to, and preferably say what exactly you don't understand. Also, it's a good idea to throw in a linebreak now and then. $\endgroup$
    – tomasz
    Sep 13 '14 at 22:34
  • $\begingroup$ I probably should, thanks for the advice. Like I said, I'm a new to the site. I'm not looking at any question in particular though. $\endgroup$ Sep 13 '14 at 22:35
  • $\begingroup$ Your argument would be correct if, say, $2^x-1$ was actually a polynomial. But by definition, a polynomial is of the form $a_n x^n + a^{n-1} x^{n-1} + \cdots + a_0$ for some parameters $a_0, \ldots, a_n$, and $2^x-1$ is not of this form. $\endgroup$ Sep 13 '14 at 22:41
  • $\begingroup$ Ah, thank you. I get it now $\endgroup$ Sep 13 '14 at 22:43

Neither of the functions you quote is a polynomial function. A polynomial function is of the form $$P(x)=a_0+a_1x+a_2x^2+\cdots + a_nx^n$$ for some constants $a_0,\ldots,a_n$.

$2^x$ is not polynomially bounded, because for any polynomial $P$ as above we have, for example, $2^{(a_0^2+a_1^2+\cdots+a_n^2+3n^2+8)^2}>P((a_0^2+a_1^2+\cdots+a_n^2+3n^2+8)^2)$.

Further, it is easy to see that any polynomial function is polynomially bounded (trivially: it is its own lower and upper bound).


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.