Show that $x^{3}$ = $O(x^{4})$ but that $x^{4}$ $\neq$ $O(x^{3})$.

  • $\begingroup$ So actually it is the other way around? O($x^{4}$) is an "umbrella" that shows $x^{3}$, which is "more efficient".. right? But how do I write this in a discrete math proof? $\endgroup$ – knowledge_is_power Nov 2 '16 at 17:31
  • 1
    $\begingroup$ The question has absolutely nothing to do with efficiency. It is about the growth rate of functions. $\endgroup$ – Yuval Filmus Nov 2 '16 at 17:39
  • $\begingroup$ We learned in Discrete Math though that we would use Big O to see which function gives us the most efficiency to see how programs run... $\endgroup$ – knowledge_is_power Nov 2 '16 at 17:41
  • $\begingroup$ @GabbyQuattrone OK but saying that big-O says that one function is more efficient than another is like saying that kilometers say that one number is longer than another. Big-O compares the growth rate of functions. If those functions are being used to measure the efficiency of programs, comparisons about growth rates tell you something about efficiency. Similarly, if numbers are being used to measure distances, comparisons between numbers tell you something about relative distances. $\endgroup$ – David Richerby Nov 2 '16 at 17:44
  • 1
    $\begingroup$ @DavidRicherby Thank you for your clarity :) $\endgroup$ – knowledge_is_power Nov 2 '16 at 17:44

We say that a function $f$ is $O(g)$ if there exist constants $M$ and $C > 0$ such that $$ x > 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 > 0$ there exists $x > M$ such that $f(x) > 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:

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

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


$x^{3}$ $\leq$ $x^{4}$ when x $>$ 0.

Let an integer k = 0 and a constant C=1 to show that $x^{3}$ is O($x^{4}$).

Let $x^{4}$ be O($x^{3}$).

Then there would exist some integer k and constant C such that $x^{4}$ $\leq$ C$x^{3}$ for all x $>$ k.

Dividing through by $x^{3}$ gives x $\leq$ C. But C is a constant, while x can be arbitrarily large, so no such C and k exist, therefore $x^{4}$ $\neq$ O($x^{3}$).

  • $\begingroup$ Try your top line with ​ x = 1/2 . ​ ​ ​ ​ $\endgroup$ – user12859 Nov 2 '16 at 18:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.