Thread: Big-O

Hello,

I'm totally confused by Big-O notation. This is the definition that I was given:

I don't understand how "k" fits into this equation. I also don't understand the significance of "C" or the relationship between the two constants (or witnesses).

I'm still thinking through this...

To prove that f(x) is big-O of g(x), do I just choose an arbitrary value for "C" that makes g(x) larger than or equal to f(x). By arbitrary I mean any value... that I have to prove that works.

And then for "k"... does that just represent the lower boundary in the domain for that value of "C" that I chose out of thin air. So "k" might actually be some value of "x" that makes f(x) = C ( g(x) ). So all values of x greater than "k" will make C ( g(x) ) greater than f(x).

My book isn't very clear about any of this and all the information on line contains formulas I don't understand anyways...

Does anyone have a simple explanation of what the formula means? Is "C" an arbitrary value or is it's value more definitive? What is "k" and what is it's relationship to "C". Right now I'm just guessing..

Thanks,
Robert

Originally Posted by lord_bunny

Hello,

I'm totally confused by Big-O notation. This is the definition that I was given:

I don't understand how "k" fits into this equation. I also don't understand the significance of "C" or the relationship between the two constants (or witnesses).

I'm still thinking through this...

To prove that f(x) is big-O of g(x), do I just choose an arbitrary value for "C" that makes g(x) larger than or equal to f(x). By arbitrary I mean any value... that I have to prove that works.

And then for "k"... does that just represent the lower boundary in the domain for that value of "C" that I chose out of thin air. So "k" might actually be some value of "x" that makes f(x) = C ( g(x) ). So all values of x greater than "k" will make C ( g(x) ) greater than f(x).

My book isn't very clear about any of this and all the information on line contains formulas I don't understand anyways...

Does anyone have a simple explanation of what the formula means? Is "C" an arbitrary value or is it's value more definitive? What is "k" and what is it's relationship to "C". Right now I'm just guessing..

Thanks,
Robert

It means that for large enough is less than (or equal) some multiple of


RonL

Hello,

To be precise, you should mention where "x" moves.
"f(x) is O(g(x)) as x goes to infinity" if there are constants C and k such that |f(x)|<C|g(x)| whenever x>k.
"f(x) is O(g(x)) as x goes to minus infinity" if there are constants C and k such that |f(x)|<C|g(x)| whenever x<k.
"f(x) is O(g(x)) as x goes to zero" if there are constants C and k such that |f(x)|<C|g(x)| whenever |x|<k.
These are used to express the asymptotic behavior of f, and it is common to omit the part "as x goes to ..." if it is clear from the context.
You usually know that |f(x)| and |g(x)| both go to infinity, but you compare their speed, how fast they grow.

For example, 2x^2+4x+5=O(x^2) (as x goes to infinity).
PROOF: Let C=3, k=10. Then, |2x^2+4x+5|<C|x^2| whenever x>k. QED

Of course, you can choose C=4, k=100 etc., they make no difference, it just says that the terms 4x and 5 are irrelevant compared to the x^2 term.
Other examples:
x^n=O(x^m) if n<m.
(any polynomial of x)=O(e^x).

Bye.

Originally Posted by wisterville

Hello,

To be precise, you should mention where "x" moves..

No, only if you are interested in something other than x large, as the usual definition is for n large.

RonL

hello my friend,

The big-O method is for approximation of complexity for large X. you can calculate it using limit also. Its to measure the progress of a function when it grows so much and by mean of that, to see how far and how fast a function grows. "C" is a constant and its not considered to have a certain effect on grow, so you can simply ignore it. Just take the largest powers of a function, since a larger power makes a function to grow more faster. it means that if there is f(x) = X^5 + 5X then you have to pick X^5 because it makes the function grows faster than any other element in that equation.
"k" is where two functions g(x) and f(x) meet eachother and since then,
g(x) becomes strictly greater than f(x) and by that |f(x)| <= C.|g(x) | for any x which is greater than k.
I had the same problem understanding this issue. have a look at my post :

http://www.mathhelpforum.com/math-he...-problems.html

PEACE and good luck