# Bachman-Landau notation and functions

• Nov 16th 2012, 10:08 AM
Nforce
Bachman-Landau notation and functions
I have a question, about Bachman-Landau. How do you know when a function fits into some notation?
For example does $x^2-6x+25$ fit into $O(x^2)$.

Or you just look and see, we had some equations in school but I cant' remember them all.

• Nov 16th 2012, 02:11 PM
emakarov
Re: Bachman-Landau notation and functions
Quote:

Originally Posted by Nforce
I have a question, about Bachman-Landau. How do you know when a function fits into some notation?
For example does $x^2-6x+25$ fit into $O(x^2)$.

For polynomials, the answer is determined by their degrees. More precisely, f(x) is O(g(x)) iff deg(f(x)) ≤ deg(g(x)). For example, x² - 6x + 25 ≤ x² + 25 ≤ 2x² for x ≥ 5, so x² - 6x + 25 is O(x²).
• Nov 17th 2012, 01:43 AM
Nforce
Re: Bachman-Landau notation and functions
Ok, I understand the degree of polynomial. But how did you get this expression:

Quote:

Originally Posted by emakarov
≤ x² + 25 ≤ 2x² for x ≥ 5, so x² - 6x + 25 is O(x²).

And what means "for x ≥ 5"
• Nov 17th 2012, 03:43 AM
emakarov
Re: Bachman-Landau notation and functions
I mean that for every x, if x ≥ 5, then x² ≥ 25. Therefore, if x ≥ 5, then x² - 6x + 25 ≤ x² + 25 ≤ x² + x² = 2x².
• Nov 17th 2012, 04:31 AM
Nforce
Re: Bachman-Landau notation and functions
Sorry but I still dont' understand, how did you get that $x^2 + 25$, and then $x^2 + x^2$. From where?

• Nov 17th 2012, 04:56 AM
emakarov
Re: Bachman-Landau notation and functions
From where I got x² + 25 and x² + x² is a separate question from whether these inequalities are true. You don't have to understand why I chose these specific expressions, but you do have to understand that if you subtract 6x from x² + 25, where x >= 5 and therefore 6x is nonnegative, then you get a smaller value than x² + 25. Therefore, x² - 6x + 25 ≤ x² + 25. Further, you have to understand that x² ≥ 25 for x ≥ 5. Therefore, if you replace 25 with a bigger value x² in x² + 25, you get a bigger result. So, x² + 25 ≤ 2x².
• Nov 17th 2012, 07:08 AM
Nforce
Re: Bachman-Landau notation and functions
Hmm, ok now I understand the ineqaulities, but why did you choose those terms? At every single expression there is one less term. So the purpose is to rewrite the function into inequalities.

At your first answer you said if deg(f()) ≤ deg(g()) is true, then the polynomial fits into O(x²), so 2 ≤ 2 is true, therefore it fits.

This is how I understand this.
• Nov 17th 2012, 08:26 AM
emakarov
Re: Bachman-Landau notation and functions
Quote:

Originally Posted by Nforce
Hmm, ok now I understand the ineqaulities, but why did you choose those terms? At every single expression there is one less term.

You are right. The definition of big-O says that we must show that for some constants $C$ and $x_0$, it is the case that $x^2 - 6x + 25\le Cx^2$ for all $x>x_0$. Therefore, the goal is to prove $x^2 - 6x + 25\le Cx^2$ for some coefficient $C$. One approach is to bound from above every term in the left-hand side by $cx^2$ for some $c$. Then you add them all together and obtain that the left-hand side is bounded from above by $(c+c'+\dots)x^2=Cx^2$.

In this example, $x^2\le1\cdot x^2$; $-6x\le 0\cdot x^2$ for $x\ge0$ and $25\le1\cdot x^2$ for $x\ge5$. Adding these inequalities, we get $x^2-6x+25\le(1+0+1)x^2$. This holds when $x\ge0$ and $x\ge5$, i.e., when $x\ge5$. Therefore, we can take $C = 2$ and $x_0=5$ and we get, as the definition of big-O demands, that $x^2 - 6x + 25\le Cx^2$ for all $x>x_0$. We could also say that $25\le25\cdot x^2$ for $x\ge1$. Then $x^2-6x+25\le(1+0+25)x^2=26x^2$ for $x\ge1$. There is some trade-off here: we got a smaller $x_0$ (1 instead of 5) but a significantly larger $C$ (26 instead of 2). If the polynomial were $x^2 + 6x + 25$ instead of $x^2 - 6x + 25$, then, since $6x\le 1\cdot x^2$ for $x\ge 6$ and $25\le x^2$ for $x\ge 5$, we could say that $x^2 + 6x + 25\le 3x^2$ for $x\ge 6$. Alternatively, since $6x\le 6x^2$ and $25\le 25x^2$ for $x\ge 1$, we have $x^2 + 6x + 25\le (1+6+25)x^2=32x^2$ for $x\ge 1$.

Still another way to prove $x^2 - 6x + 25$ is $O(x^2)$ is to plot the graphs of the two functions and to note that $x^2$ eventually dominates $x^2 - 6x + 25$. (If it did not, then we should plot $2x^2$, $3x^2$, etc. until it dominates the left-hand side). Then we can solve $x^2 - 6x + 25\le x^2$ to get $x\ge 25/6$. Thus, we can take $C = 1$ and $x_0=25/6$.

Quote:

Originally Posted by Nforce
At your first answer you said if deg(f()) ≤ deg(g()) is true, then the polynomial fits into O(x²), so 2 ≤ 2 is true, therefore it fits.

This is correct, but this is a general theorem, and I am not sure you can provide the proof (though it is basically a generalization of the reasoning above). Whether this is sufficient depends on your course. It is possible that you need a way to show that $x^2 - 6x + 25$ is $O(x^2)$ that you can fully justify.

• Nov 17th 2012, 11:33 AM
Nforce
Re: Bachman-Landau notation and functions
This is the best answer. Thank you. Another thing, what do you mean by "one function dominates another"? Does it mean that one function increases faster then another?
• Nov 17th 2012, 12:21 PM
emakarov
Re: Bachman-Landau notation and functions
Quote:

Originally Posted by Nforce
Another thing, what do you mean by "one function dominates another"? Does it mean that one function increases faster then another?

Here by " $f(x)$ eventually dominates $g(x)$" I mean that $f(x)\ge g(x)$ "eventually," i.e., for all $x$ starting from some point $x_0$. That is, if $g'(x)$ is $O(f'(x))$, then there exists a constant $C > 0$ such that $Cf'(x)$ dominates $g'(x)$ (assuming that $f'(x)$ and $g'(x)$ are nonnegative). But, as far as I know, "dominates" does not have a universally accepted precise meaning in mathematics.