# Formally proving that a function is $O(x^n)$

Say I have a function $f(x) = ax^3 + bx^2 + cx + d$ where $a > 0$.

It's clear that for a high enough value of $x$, the $x^3$ term will dominate and I can say $f(x) \in O(x^3)$, but this doesn't seem very formal.

The formal definition is $f(x) \in O(g(x))$ if constants $k, x_0 > 0$ exist, such that $0 \le f(x) \le kg(x)$ for all $x > x_0$.

My question is, what are appropriate values for $k$ and $x_0$? It's easy enough to find ones that apply (say $k = a + b + c + d$). By the formal definition, all I have to do is show that these numbers exist, so does it actually matter which numbers I use? For some value of $x$, $k$ could be anywhere from $1$ to $a + b + c + d + ...$. From my understanding, it doesn't matter what numbers I pick as long as they 'work', but is this right? It seems too easy.

Thanks

-
I changed some of the c's to k's because I think there was a clash there - hope that it was correct to do so. –  anon Sep 25 '10 at 16:57
Looks fine to me. You missed one though -- I fixed it :-P –  Joel Sep 25 '10 at 17:03
If $a < 0$, then the $0 \le kg(x)$ is violated... Perhaps a different definition? Or can $k < 0$? –  Aryabhata Sep 25 '10 at 18:54
@Moron: Yeah, I think we should have $|f(x)|<k|g(x)|$ for $x>x_0$. For instance, $sin(x)=O(1)$ and the defintion by Joel doesn't give this. –  alext87 Sep 25 '10 at 18:58
@alex: Yeah, since this seems like homework, just trying to make sure Joel knows the right definition taught in their class :-) –  Aryabhata Sep 25 '10 at 19:03

The argument you are getting at as I understand is is, roughly: $x^n \in O(x^n)$ and thus $kx^n \in O(x^n)$, so $f(x)$ acts like $O(x^3) + O(x^2) + O(x) + O(1)$ which can be reduced to $O(x^3)$.

So the theorem we would like to prove now is that for $n\geq m$: $f \in O(x^n)$ and $g \in O(x^m)$ implies $f + g \in O(x^n)$. Once we have this you just add up the monomials of the polynomial and that proves the result.

Look at what we have, from the definitions:

$$f \in O(x^n) \Rightarrow \exists x_0, k,\;\; \forall x>x_0,\;\; f(x) \leq kx^n$$

$$g \in O(x^m) \Rightarrow \exists x_1, k',\;\; \forall x>x_1,\;\; g(x) \leq kx^m$$

Let $x_2$ be the maximum of $x_0$ and $x_1$, $k''$ be the maximum of $k$ and $k'$ and add these inequalities:

$$\forall x>x_2,\;\; (f+g)(x) \leq kx^n + k'x^m \leq k''(x^n + x^m) \leq 2 k'' x^n$$

Now the pair of values $(x_2,2k'')$ prove that $f+g \in O(x^n)$.

To consider abstract functions like this makes the proof very easy, but it is clear that the values we exhibit to prove the existential may not be the best, although we still prove the theorem in an effective way. In particular, you could do a very detailed analysis of the functions in specific cases to get very tight bounds - in this lucky case it's not needed which is why the theorem is easier to prove in the abstract case.

-

HINT $\quad\rm ax^3 + bx^2 + cx + d\ \le \ (|a|+|b|+|c|+|d|)\ x^3 \$ for $\rm\ x > 1$

-

Suppose you have a function $f(x)$ and $g(x)$.

A really simple method (that works when $f(x)$ and $g(x)$ are polynomials) of determining a constant that works is the following. Consider

$\lim_{x\rightarrow\infty}\frac{f(x)}{g(x)}$

If the limit exists and if a constant $0\leq C< \infty$. Then $C+\epsilon$ for any $\epsilon>0$ is a constant that works. To see this just apply the definition of the limit. $\forall \epsilon>0$ there exists a $x_0(\epsilon)$ such that $\forall x>x_0(\epsilon)$ we have

$\left|\frac{f(x)}{g(x)}-C\right|<\epsilon$

That is

$\frac{f(x)}{g(x)} < C+\epsilon$

Now you know the constant from calculating the limit and know the existence of $x_0$. Since you are always considering asymptotics when using this definition you are never concerned with the value of $x_0$ (only that it exists)

It does not matter what constants you use and someone could easily use different constants to get $f(x)=O(g(x))$. This notation is to compare the growth rate of two functions.

If $\lim_{x\rightarrow \infty} \frac{f(x)}{g(x)}$ does not exist or is hard to calculate then as long as you can bound it above you still have $f(x)=O(g(x))$

-