Joe Neidermeier
Joe Neidermeier

Reputation: 1

Trouble understanding the constant portion of Big O

Can someone explain to me the purpose of the constant portion of big O notation?

I'll try and explain where I am at right now in terms of understanding:

Basically you have a function, for example f(x) = x^2 + 1 and g(x) = x^3

So, f(x) is O( g(x) ), because for a certain value of x, k, for every x > k , f(x) <= **C**|g(x)|.

So for this equation, k = 2.

I could be wrong already so please correct me if so.

That seems intuitive enough, but I get a little bit confused about the constant value, C.

Upvotes: 0

Views: 100

Answers (2)

cdiggins
cdiggins

Reputation: 18233

The following line is poorly phrased:

f(x) is O( g(x) ), because for a certain value of x, k, for every x > k , f(x) <= C|g(x)|

The following is more accurate:

f(x) is O( g(x) ), because there exists a value k and a value C such that for any value of x greater than k: f(x) <= C|g(x)|.

I hope this helps.

Upvotes: 2

David Grayson
David Grayson

Reputation: 87486

It's just some constant. To prove f(x) is O(g(x)) you must pick some specific constants C and k and prove they satisfy that condition. What's so confusing?

Upvotes: 0

Related Questions