There is a definition in my notes and says,

When functions are polynomially bounded, the initial conditions (the value on small inputs) do not make a difference for the solution in asymptotic notations. The initial conditions can make a difference, when the function is not polynomially bounded.

Can somebody explain what that means? Thank you


If a function $f$ is polynomially bounded it means there exists polynomials $g$ and $h$ such that for all $x$, $$g(x)\le f(x)\le h(x).$$

  • $\begingroup$ Isn't there always a function h(x) that is greater than f(x)? Can you give an example of a polynomially unbounded function? $\endgroup$ Mar 20 '13 at 23:32
  • $\begingroup$ E.g. $e^x$. Remember the inequality has to hold for all $x$. $\endgroup$ Mar 20 '13 at 23:34
  • $\begingroup$ @bigO: $x\mapsto 2^x$ is not polynomially bounded. $\endgroup$ Mar 20 '13 at 23:34
  • $\begingroup$ @HenningMakholm forr example, if we choose h(x)=3^x, doesn't the inequality hold? I couldnt get the point $\endgroup$ Mar 20 '13 at 23:37
  • 4
    $\begingroup$ @bigO: $3^x$ is not a polynomial! $\endgroup$ Mar 20 '13 at 23:37

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.