What is the value of C in $O(x^n)$ definition?

Question

I read the definition that $f$ is in $O(x^n)$ if $|f(x)|<C|x^n|$ for some $C$.

I'm struggling to understand how to check this. For example, supposedly $f(x) = 5x+3x^2$ is in $O(x)$ but not $O(x^2)$?

If I plot $f(x) = 5x + 3x^2$ and $g(x)=x$ I see that the first goes to infinity much quicker.

If I let $g(x) = Cx$, and plot $C=1,C=10, C=20, C=100$, it looks like it overcomes $f$ for $C>10$:

But, if you zoom out further, you can see that's not true:

So, I know it doesn't matter what $C$ is, but how can I show that there exists a $C$ to make the definition hold so that I can tell if $f$ is in $O(x^n)$?

If you go out far enough, and $C$ is large enough can't I make either $f$ or $g$ as close to the y-axis as I want?

Answer 1

The definition is not complete since the inequality is supposed to hold for all $x>k$ where $k$ is a constant. The idea behind the $\mathcal O$-notation is to provide an estimate (comparison) for large $x$. This makes life much easier for your example since $x < x^2 \ \forall\, x>1$, so that

$0<f(x)= 5x+3x^2<5x^2+3x^2=8x^2 \ \forall \, x>1$

So you might choose $C:=8$ and $k:=2$ here in order to see that $f\in\mathcal O(x^2)$. By the way, this statement can be generalized to hold for polynomials of degree $n$, i.e. if $f\in \mathcal P_n$ then $f\in\mathcal O(x^n)$.

Answer 2

The function $f(x) = 5x + 3x^{2} \not \in O(x)$, but it is in $O(x^{2})$. The way you show that $f(x) \in O(x^{2})$ is by picking a constant $C$ and appropriate constant $k$ such that $|f(x)| \leq Cx^{2}$ for all $x \geq k$.

Big-O can often be ascertained using limits. If the following condition holds:

$$L = \lim_{x \to \infty} \dfrac{f(x)}{g(x)} < \infty$$

Then we have that $f(x) \in O(g(x))$. The converse does not necessarily hold, as given in the comments below ($x*sin(x)$).

So consider:

$$\lim_{x \to \infty} \dfrac{5x + 3x^{2}}{x} = 5 + \lim_{x \to \infty} 3x = \infty$$

And:

$$\lim_{x \to \infty} \dfrac{5x + 3x^{2}}{x^{2}} = 0 + 3 = 3$$

Thus, $f(x) \in O(x^{2})$ but not $O(x)$.

You can check out these links for more information on how to formulate Big-O proofs: http://www.dreamincode.net/forums/topic/280815-introduction-to-proofs-induction-and-big-o/ http://www.dreamincode.net/forums/topic/321402-introduction-to-computational-complexity/