Is the function polynomially bounded? Is the function polynomially bounded?

We will use the following facts in this proof:

  1. (eqn. (3.18) see Exercise 3.2-3)
  2. because for any and for all


If a function is polynomially bounded then there exist constants such that for all , . Hence, , i.e. if a function is polynomially bounded, then and vice versa.

We can analyze as follows:

The last line comes from the fact that, for , . Hence, asymptotically is definitely larger than . In other words, , i.e. is not polynomially bounded.

We can analyze as follows:

The last line comes from the fact that, , i.e. logarithmic functions are polynomially bounded.

Hence, asymptotically is definitely smaller than . In other words, , i.e. is polynomially bounded.

If you have any question or suggestion or you have found any error in this solution, please leave a comment below.