Show whether $ x^3$ is $O(g(x))$ where $g(x)=x^2 $

Question

I know that $x^3$ is $O(x^3)$ or any exponent higher than 3, but how do I show mathematically that $x^3$ is not $O(x^2)$?

Answer 1

If you want to show that it's NOT the case that $x^3=O(x^2)$, then you are showing that $x^2=o(x^3)$, or in other words, that $x^2$ is "little-oh" of $x^3$, which communicates that $x^2$ is of a smaller order of growth than $x^3$.

As gimusi has noted, you could show $x^2=o(x^3)$ via limits as follows

$$\lim_{x\rightarrow \infty} \frac{x^3}{x^2}=\lim_{x\rightarrow \infty} \frac{3x^2}{2x}=\lim_{x\rightarrow \infty} \frac{6x}{2}=\lim_{x\rightarrow \infty}\frac{6}{2}x=\lim_{x\rightarrow \infty}3x=3\lim_{x\rightarrow \infty}x=3\cdot \infty =\infty$$

*Note the use of of L'Hopital's Rule since $\lim_{x\rightarrow \infty} \frac{x^3}{x^2}=\frac{\infty}{\infty}$ in the beginning

---

We could also show this using the definition of "big-oh." Consider that $f(x)=O(g(x))$ iff there exists constants $c,k$ such that $|f(x)| \le c \cdot |g(x)|$ for all $x>k$.

Let $f(x)=x^3$ and $g(x)=x^2$ and assume $x^3=O(x^2)$. Hence, by definition of big-oh, there exists constants $c,k$ such that

$$|x^3|\le c \cdot |x^2|$$

for all $x>k$. Note that $x^2>0$ and $x^3>0$ as $x\rightarrow \infty$, so we can remove the absolute value signs, having

$$x^3 \le c \cdot x^2$$

Now,

$$\frac{1}{x^2}x^3\le c \cdot x^2\frac{1}{x^2}$$ $$\Rightarrow x \le c$$

By the trichotomy law, for constants $c,k$ we know either $c=k$, $c<k$, or $k<c$.

Case i. $c=k$

By substitution we have $x \le k$. But we already stated $x>k$. Hence, we have contradiction.

Case ii. $c<k$

If $c<k$ and $x \le c$, we have $x < k$. But we already stated $x>k$. Hence, we have contradiction.

Case iii. $k<c$

Recall that $x \le c$ for ALL $x>k$. So whenever $x>c>k$, we have a contradiction.

Thus, if we assume $x^3=O(x^2)$, then in all cases we have a contradiction. Therefore, it is NOT the case that $x^3=O(x^2)$, and it is true that $x^2=o(x^3)$.

Answer 2

Simply recall the definition and note that

$$\lim_{x\to \infty} \frac{x^3}{x^2}= \infty$$

Answer 3

If $x^3 = O(x^2)$, then there is a $c > 0$ and an $x_0$ such that $x^3 < cx^2$ for $x > x_0$.

But this implies that $x < c$ which is false for $x > \max(c, x_0)$.

Therefore $x^3 \ne O(x^2)$, or $x^3 \not\in O(x^2)$.