Big-Oh Pendantry

Now everybody knows big-Oh notation, right? If you study computer science you learn about it in the first year, if not the first semester. Please allow me to be pedantic for a second.

First of all – and you see this a lot, to the extent that I would say this is actually accepted notation, but I will silently judge you – technically, $O(\cdot)$ is a set of functions. So if you write something like $42n^2 = O(n^2)$, well, hm, that’s a type error. You could use $42n^2 \in O(n^2)$, but I admit that does feel very pedantic even to me. I tend to write the word “is” as follows: $42n^2$ is $O(n^2)$. Maybe that’s me being Dutch, but here we are.

Secondly, don’t leave constant factors in the big Oh, like $O(2n)$. This is one I only see students do and, like, technically you’re not wrong. But I would say there is basically zero tolerance for writing this in a paper unless you’re doing it to make a very particular point. As a student myself I once forgot to simplify $\sqrt4$ on an exercise sheet. Similar thing: it’s not wrong, per se, but it’s certainly a silly way to write 2.

Finally, $O(\cdot)$ technically needs to know which variable is going to infinity. Usually this is obvious from context, but I find $O(1)$ particularly funny in this sense: it should kind of be $O(\lambda n . 1 )$, right? Nobody is going to write that, of course, but I do want you to make sure that it actually is clear from context: sometimes there are multiple variables (or no visible variables at all). And I did call this episode “pedantry,” you see. I cover my bases like that.