Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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.


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.


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


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.


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.




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: