Is it true that x^3 is O(g(x)), if g is the given function?
  1. x^2
  2. x^3
  3. x^2+x^3
  4. x^2+x^4
  5. 3^x
  6. x^3/2
It should, by now, be clear that the answer is yes for all but possibly the first (in each case C=2 and k=3 from the definition will work). Note, for g(x)=3^x we could say the following: we can take for granted that x^3 is O(2^x) and 2^x< 3^x for all x> 1, hence we are done by Exercise 17 (which you should now do). Let us check that the answer is no for g(x)=x^2

Similar to previous problems, from the definition, can there be some C,k such that for all x> k
x^3< C*x^2? Divide both sides by x^2 (which is OK so long as x is bigger than 0) we get
x< C which obviously does not hold for all x> k.