1

I am stuck on a proof question involving the big-O notation:

Prove that if $f(x)$ is $O(x^3)$ then $f(x+x^2)$ is also $O(x^3)$.

I am stuck because $f(x)$ can be any arbitrary polynomial. I started off with defining $f(x)$ as a polynomial of the nth order with arbitrary constants of $a_0, a_1, \ldots, a_n$. For $f(x+x^2)$ I substituted in $x+x^2$ in place of the $x$ for the polynomial defined for $f(x)$ but I am stuck on simplifying the result.

Help would be much appreciated :)

mathnoob
  • 21

1 Answers1

1

Since $f(x)$ is $O(x^3)$ there is some $M$ such that $\left| \frac{f(x)}{x^3} \right|\leq M$ when $x$ is large enough.

Using with $x+x^2$ instead of just $x$, given that $x$ is large enough, $$\left| \frac{f(x+x^2)}{(x+x^2)^3}\right|\leq M $$

For $x$ large enough, $\frac{x+x^2}{x^3}\leq 1$ hence $$\left| \frac{f(x+x^2)}{x^3}\right|\leq \left| \frac{f(x+x^2)}{x+x^2}\frac{x+x^2}{x^3}\right|\leq \left| \frac{f(x+x^2)}{(x+x^2)^3}\right|\leq M $$

Gabriel Romon
  • 35,428
  • 5
  • 65
  • 157