Determine whether $x^3$ is $O(g(x))$ for certain functions $g(x)$.

Question

a) $g(x) = x^2$

b) $g(x) = x^3$

c) $g(x) = x^2 + x^3$

d) $g(x) = x^2 + x^4$

e) $g(x) = 3^x$

f) $g(x) = (x^3)/2$

Do you guys have any ideas? Thanks!

Answer 1

Since you asked in a comment about (e), let's discuss that.

Saying "$x^3$ is $O\bigl(3^x\bigr)$" means the following:

There is some constant $c$, such that for all sufficiently large $x$, $$x^3 < c\cdot3^x.$$

Consider the functions $x^3$ and $3^x$. Clearly, $3^x$ increases much faster than $x^3$. For $x=10$, $3^x$ is already 59,049 and $x^3$ is only 1,000. And $3^x$ triples every time $x$ becomes $x+1$, whereas $x^3$ does not triple so easily; to triple $x^3$ you have to multiply $x$ by something.

So there is no trouble finding the constant $c$ that we want; $c=1$ will do. And indeed, for all $x>10$, it is the case that $x^3 < 1\cdot 3^x$. So $x^3$ is $ O\bigl(3^x\bigr)$.

Now on the other hand, $x^3$ is not $O\bigl(x^2\bigr)$. Why not? Well, if it were, then

There is some constant $c$, such that for all sufficiently large $x$, $$x^3 < c\cdot x^2$$

But clearly that's not true, since no matter what $c$ is, $x^3 > c\cdot x^2$ whenever $x>c$. So $x^3$ is not $O\bigl(x^2\bigr)$.

Does that help?

Answer 2

As $x\to\infty $ :

Well , for polynomials you should just look at the term with highest degree.

Positive coefficients are negligible.

And $a^x$ always dominate polynomials in the long run for $a>1$..

So , for your question :all possible except a...

Answer 3

You can use the following result

$$f=O(g) \iff \limsup_{x \to \infty}\frac{|f(x)|}{|g(x)|} =c,$$

where $c$ is finite.