# What is a polynomially bounded function?

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?

Thanks

• 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. Sep 13 '14 at 22:34
• 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. Sep 13 '14 at 22:35
• 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. Sep 13 '14 at 22:41
• Ah, thank you. I get it now 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)$.