# Show that x^3 is O(x^4) but that x^4 is not

Show that ${x}^{3}$ is $O\left({x}^{4}\right)$ but that ${x}^{4}$ is not $O\left({x}^{3}\right)$.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

Jack Maxson
Defintions
Big-O Notation: $f\left(x\right)$ is $O\left(g\left(x\right)\right)$ is there exists constants C and k such that
$|f\left(x\right)|\le C|g\left(x\right)|$
Whener x>k
Note: Choises of C and k are not unique.
Solution:
First part
$f\left(x\right)={x}^{3}$
$g\left(x\right)={x}^{4}$
For convevience sake, we will choose k=1 and thus x>1.
$|f\left(x\right)|=|{x}^{3}|$
$={x}^{3}$
$1\cdot {x}^{3}$
$
$={x}^{4}$
$=|{x}^{4}|$
Thus we need to choose C to be at least 1. Let us then take C=1
By the definition of Big-O notation, $f\left(x\right)={x}^{3}$ is $O\left({x}^{4}\right)$ with k=1 and C=1.
Second part
$f\left(x\right)={x}^{4}$
$g\left(x\right)={x}^{3}$
Let us assume that $f\left(x\right)={x}^{4}$ is $O\left({x}^{3}\right)$. Then there exist constants C and k such that:
$|{x}^{4}|\le C|{x}^{3}|$
when x>k
Let us assume $C\ge 0$, which is a safe assumption.
$|{x}^{4}|\le C|{x}^{3}|=|C{x}^{3}|$
We have then obtained a contradiction, because $|{x}^{4}|>|C{x}^{3}|$ when x>C
Thus $f\left(x\right)={x}^{4}$ is not $O\left({x}^{3}\right)$