Is it true that x^3 is O(g(x)), if g is the given
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.