What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics

I think the confusion is because strictly speaking $f(x) = O(g(x))$ is an abuse of notation. $O(g(n)), \Theta(g(n))$ and friends are sets. We can't say that a function equals a set, or that a function "is less" than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error.

Here "is less" is interpreted as "eventually less for all values" and "plus a set" is interpreted as "plus any function of that set".

I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it's just notation in the end.

> computer science students should be familiar with the standard f(x)=O(g(x)) notation

I have always thought that expressing it like that instead of f(x) ∈ O(g(x)) is very confusing. I understand the desire to apply arithmetic notation of summation to represent the factors, but "concluding" this notation with equality, when it's not an equality... Is grounds for confusion.

Maybe an easier explanation: just subtract g(x) from both sides.

You get:

  f(x) - g(x) ≤ O(1)

  f(x) - g(x) = O(1)

  f(x) - g(x) ≤ O(1)

The easiest way to read it is "there exists a function h in O(1) such that f(x) <= g(x) + h(x)."

I think first we should teach "f in O(g)" notation, then teach the above, then observe that a special case of the above is the "abuse of notation" f(x) = O(g(x)).

You do things a bit different on an actual computer, right. As x cannot tend to infinity (so everything is O(1) by that measure) so common sense is applied.

O(1) just means "a bounded function (on a neighborhood of infinity)". Unlike f(x), which refers to some function by name, O(1) refers to some function by a property it has. It's the same principle at work in "even + odd = odd".

Programmers wringing their hands over the meaning of f(x)=O(g(x)) never seem to have manipulated any expression more complex than f(x)=O(g(x)).

[dead]

[dead]