Find witnesses proving that $f(x) = 2x^3 + x^2 + 5$ is $O(x^3 )$.

Question

Find witnesses proving that $f(x) = 2x^3 + x^2 + 5 \textrm{ is } \mathrm{O}(x^3 )$.

What do i need to do here?

Like step by step?

Answer 1

You need to find constants $C$ and $N$ (these are your witnesses) such that $$|f(x)| \leq C|x^3|$$ for all $x \geq N$.

An easy way to do this is change all of the variables in your polynomial to the highest occuring power, that is $$f(x) = 2x^3 + x^2 + 5 \leq 2x^3 + x^3 + 5x^3 = 8x^3,$$ so we can take $C = 8$ and $N = 1$, which will be your witnesses.

Answer 2

That $f(x) = O(x^{3})$ means that there are some $M \geq 0$ and some $X \in \mathbb{R}$ such that $|f(x)| \leq M|x^{3}|$ for all $x \geq X$. But, since $$\frac{f(x)}{x^{3}} = 2 + \frac{1}{x} + \frac{5}{x^{3}} < 3$$ for large $x$, we are done.