<= vs < when proving big-o notation

We just started learning big-o in class. I understand the general concept that开发者_StackOverflow f(x) is big-o of g(x) if there exists two constants c,k such that for all x>k |f(x)|<=c|g(x)|. I had a question whether or not it is required that we include the <= to sign or whether it is just sufficient to put the < sign?

For example: suppose f(x)=17x+11 and we are to prove that this is O(x^2). Then if we take c=28 and x>k=1 we know that 17x+11<=28x^2. So since we know that x will always be greater than 1 this implies that 28x^2 will always be greater than 17x+11. So, do we really need to include the equal sign (<=) or is it okay if we just write (<)?

Thanks in advance.

From |f (x)| ≤ c |g (x)| for some real-valued c, it follows that |f (x)| < (c + e) |g (x)| for all e > 0.

From that it follows that there exists c' = (c + e) such that |f (x)| < c' |g (x)|, so you can use < instead of ≤.

More practically, if you can prove |f (x)| < c |g (x)|, the ≤ part follows trivially.

If you have shown x < y then you have also shown x <= y. So it makes no difference.

whether or not it is required that we include the <= sign or whether it is just sufficient to put the < sign?

There are two slightly different things you're asking here, I think:

• If you can demonstrate a c and k such that for all x > k |f(x)| <= c|g(x)|, then trivially you have also demonstrated a c and k such that for all x > k |f(x)| < c|g(x)|. So showing < is sufficient, but:

• As you've stated, the actual requirement for being able to say f(x) = O(g(x)) is to find a c and k such that for all x > k |f(x)| <= c|g(x)|. If the best we can do is find a c and k such that for all x > k |f(x)| = c|g(x)|, then we haven't met your < condition, but we have done enough to show f(x) = O(g(x)). So showing < is not necessary

You can't replace <= with < in the definition.

Any function f that's infinitely often zero is O(f), but not if you replace <= with <.

For example, let f(x) = x if x is odd, 0 if x is even. Then f is O(f) because f(x) <= f(x) for all x. However, there's no c such that f(x) < cf(x) for all large x, because both sides are 0 for all even x.

It is not ok to use < instead of ≤, although it is obvious that they are -in some cases- identical, because ≤ is part of the Big-O notation definition.

On the other hand, the definition: 0 ≤ f(n) < cg(n) belongs to a different class (the Little-o notation) which is included in the Big-O class