alt Hacker NewsI 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.
Replies
To me it seems similar to the + C on an antiderivative (or more generally, quotient objects). Technically, you are dealing with an equivalence class of functions, so a set. But it's usually counterproductive to think of it that way (and when you study this stuff properly, one of the first things you do is prove that you (usually) don't need to, and can instead use an arbitrary representative as a stand-in for the set), so you write F(x)+C.
>but notoriously mathematics runs on javascript
Lean is much more notorious for mathematics.
when '=' is used, it no longer means "set", but "some element of that set" instead
Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you'd get plenty of junk theorems from that fact.
I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics -
A coset, quotients r + I, affine subspaces v + W, etc. Not literal sets but comparing some representative with a class label, and the `=, +` is defined not just on the actual objects but on some other structure used to make some comparison too.
The reason it's preferred to use "=" instead of "\in" is because the way that Landau notation is generally used in practice is as a kind of ellipsis or placeholder. For example, the Taylor expansion e^x = 1 + x + O(x^2). I could just as well write e^x = 1 + x + ..., but the former conveys more meaning about what is hidden behind the ellipsis. It's an abuse of notation, but in the contexts that it's used, it's not clear what additional clarity using "\in" would bring over "=". Maybe also that big O is mainly used as a notation to facilitate doing calculations, less describing what family a function belongs to. Here are Knuth's thoughts, which I agree with: https://micromath.wordpress.com/2008/04/14/donald-knuth-calc...