Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$

Question

Show that $(x^3+2x)/(2x+1)$ is $O(x^2)$

The definition says:

We say that $f(x)$ is $O (g(x))$ if there are constants $C$ and $k$ such that $$\mid f(x) \mid \leq C \mid g(x) \mid$$ whenever $x > k$.

I am new to this can someone help me?

Answer 1

You want to demonstrate that there are $x_0>0$ and $M>0$ such that for all $x\geq x_0$ $|(x^3+2x)/(2x+1)|\leq Mx^2$. For large positive $x$, we have $x^3+2x\geq 0$ and $2x+1>0$ and so $$ \left|\frac{x^3+2x}{2x+1}\right|\leq Mx^2\iff x^3+2x\leq (2x^3+x^2)M. $$ Note also that for $x\geq 4$, $x^2\geq 4x$. And so $M=\frac{1}{2}$ is enough the rightmost inequality above. It remains to pick $x_0$ such that $x\geq x_0$ implies $x^3+2x\geq 0$, $2x+1>0$ and $x\geq 4$. In particular, $x_0=4$ works.

The above demonstrates a way to come up with $x_0$ and $M$. Now to be rigorous (and perhaps more coherent), you should verify the definition of $O(\cdot)$ starting with these $x_0$ and $M$.

Answer 2

Expanding on my hint above, this is one way to prove the result from first principles:

$$\frac{x^3 + 2x}{2x + 1} = {x^2 \over 2} - {x \over 4} - {9 \over 8} + {9 \over 8(2x + 1)} \ \ \ \ \ \ - (*) $$

hence

$$\left|\frac{x^3 + 2x}{2x + 1} \right| \leq {x^2 \over 2 } + \left| x \over 4\right| + {9 \over 8} + \left|9 \over 8(2x + 1) \right|$$

Now we want to find values of $C$ and $k$ such that each term is bounded:

• For $x > k_1$, ${x^2 \over 2 } \leq C_1x^2$

• For $x > k_2$, $\left| x \over 4\right| \leq C_2 x^2$

• For $x > k_3$, $9/8 \leq C_3 x^2$

• For $x > k_4$, $\left|9 \over 8(2x + 1) \right| \leq C_4 x^2$

Once we have those values of $C$ and $k$, it then follows that

$$ x > K = \max(k_1, k_2, k_3, k_4) \ \text{ implies } \left|\frac{x^3 + 2x}{2x + 1} \right| \leq C' x^2$$

where $C' = C_1 + C_2 + C_3 + C_4$.

The 'good' thing about asymptotic analysis like this is we don't care how strict the bounds are; we just need to have them. So use any approximations you want to find the values of the $C$s and $k$s.

For example,

$k_1 = 0, C_1 = 1/2$ (obvious!);

$k_2 = 1, C_2 = 1$;

$k_3 = 1, C_3 = 3/2$;

$k_4 = 1, C_4 = 1$.

Hence $K = \max(0,1,1,1) = 1$ and $C' = 1/2 + 1 + 3/2 + 1 = 4$ and we have

$$x > 1 \ \ \text{ implies } \left|\frac{x^3 + 2x}{2x + 1} \right| \leq 4x^2$$

---

If you don't have to prove the result from first principles, i.e., if you already have the results that $x^p = O(x^q)$ for all $p \leq q$ and that $f_1(x) = O(g(x))$ and $f_2(x) = O(g(x))$ implies $f_1(x) + f_2(x) = O(g(x))$, then you use those results on equation (*) above.

Answer 3

Substituting the particular expressions of $f$ anf $g$, you need to find $C$ and $k$ such that

$$x>k\implies\left|\frac{x^3+2x}{2x+1}\right|\le C|x^2|,$$ or after rewriting, assuming $x>0$ $$\left|x^2+2\right|\le C|2x^2+x|,$$ $$0\le(2C-1)x^2+Cx-2.$$ The RHS grows to infinity when $2C-1\ge0$. Let us choose the minimum value $C=\dfrac12$. Then $$0\le\frac x2-2$$ is true with $x>k=4$.