What is a polynomially bounded function?

2.3k Views Asked by At

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

1

There are 1 best solutions below

0
On BEST ANSWER

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