Show that $x^3 = O(x^4)$ and $x^4 \neq O(x^3)$
We say that a function $f$ is $O(g)$ if there exist constants $M$ and $C &gt; 0$ such that
$$
 x &gt; M \Longrightarrow f(x) \leq C g(x).
$$

It shouldn't be too difficult to show that $x^3$ is $O(x^4)$ using the definition.



To show that $f$ is not $O(g)$ you need to show that for every $M$ and $C &gt; 0$ there exists $x &gt; M$ such that $f(x) &gt; C g(x)$. While using this to refute "$x^4$ is $O(x^3)$" is a bit awkward, I think that it's a good exercise which is not too difficult.

Later on you might learn other ways of showing that $f$ is not $O(g)$. Very briefly, the idea of the other methods is a two-pronged attack:


If $f$ is $O(g)$ then X.
X is false.
Therefore $f$ is not $O(g)$.


I'll let your professor give you examples of X.