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