Hacker News Reader

Comment by roywiggins | Hacker News Reader

CS already abuses equality all the time with big-O notation. Often you see stuff like f(n) = O(N²), when they mean that f ∈ O(N²). It's fine because everyone knows what's going on, but it's not using it in the sense of equality.

View on HN

Sigh; it seems it's only programmers who think CS has a monopoly on big-O notation, or keep calling it abuse of notation and trying to use ∈, when it's really = that's the standard notation in mathematics (and for good reason).

Before Knuth popularized Big O notation in CS and started the field of analysis of algorithms, already in 1958 N. G. de Bruijn wrote an entire book on Asymptotic Methods in Analysis (not CS): see a few of its leading pages here: https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a...

And the notation was already being used by Bachmann in 1894 and Landau by 1909 in analytic number theory, well before computers. It was perfectly commonplace to use big-O notation with the equals sign very quickly: see e.g. this paper by Hardy and Littlewood (https://projecteuclid.org/download/pdf_1/euclid.acta/1485887...) from 1914, well before even Turing machines or lambda calculus were formulated, let alone actual computers or analysis of algorithms.

Mathamaticians also abuse big-O in a simmilar way.

For instance we might say:

    sin(x) = x -x^3/6 + x^5/120 + O(x^7)

To indicate that the terms we did not write are in O(x^7). Also note that, in this case, we are actually looking at big-O as x->0.

The statement about sine above is not something mathematicians would write. It makes little sense to use big-O notation in this context, as it doesn't say anything useful here: the O(x^7) element absolutely dominates the remaining explicit elements of lower order, so including them tells us absolutely nothing. In fact, sin(x) = O(1).

However, mathematicians do indeed use similar notation in this context, that is, little-o notation. It is in fact true that

sin(x) = x -x^3/6 + x^5/120 + o(x^5), x -> 0.

https://en.wikipedia.org/wiki/Taylor_series#First_example

https://www.wolframalpha.com/input/?i=taylor+series+sin+x

Notice that in your example, you have o(x^5) and an explicit x^5 term. In my example I have O(x^7), but no explicit x^7 term. It is true that I cannot think of a circumstance where you want to do this abuse of notation and would care if you were forced to use little-o or big-O instead of the other.

In my experience, it happens to be more common to use big-O.

I have definitely used big-O as the parent described. I think many mathematicians would write it in that way.

Have you considered that higher orders of x are in fact smaller when x is near 0?

The parent comment was right and you are wrong, around zero x^5 absolutely dominates x^7 and the big-O notation is used. See for example here [1]

[1] https://en.wikipedia.org/wiki/Taylor_series#First_example

Sure it is, O notation denotes equivalence classes and being part of the same equivalence class is a perfectly cromulent notion of equality.

Big-theta gives you equivalence classes. Big-O only gives you partial ordering.

For instance, we might say x = O(x^2) and x=O(x), but we would not say O(x^2)=O(x).

Interestingly, in my experience, some people will actually say O(x)=O(x^2), but that seems a bit too abusive for my liking.

Yea, my mistake :)

I was taught to use tilde in big-O notation. Your use of "set element" operator is not quite correct either, because of the limit that's going on there.

I don't think the limit is really an issue here. Most CS textbooks define big-O with the limit ->infinity part baked into the definition. So, this is more of an issue of different people using different definitions than an issue of abuse of notation.

Reply on news.ycombinator.com