Question

Show that whether x5 + 10x3 + x + 1 is O(x4) or not?

Answer 1

Let us show by contradiction that $x^5 + 10x^3 + x + 1$ is not $O(x^4)$. Suppose that $x^5 + 10x^3 + x + 1$ is $O(x^4)$. Then there exist a constant $C$ and $x_0$ such that $x^5 + 10x^3 + x + 1\le Cx^4$ for all $x\ge x_0.$ It follows that $\frac{x^5 + 10x^3 + x + 1}{x^4}\le C$ for all $x\ge x_0.$

Since $\lim\limits_{x\to\infty}\frac{x^5 + 10x^3 + x + 1}{x^4} =\lim\limits_{x\to\infty}(x+\frac{10}{x}+\frac{1}{x^3}+\frac{1}{x^4})=\infty,$ we conclude that there exists $x_1>x_0$ such that $\frac{x_1^5 + 10x_1^3 + x_1 + 1}{x^4}> C.$ This contradiction proves that $x^5 + 10x^3 + x + 1$ is not $O(x^4)$.