Why is it O(1) (and not, say, O(2))?

If the running time of an algorithm scales linearly with the size of its input, we say it has $O(N)$ complexity, where we understand N to represent input size.

If the running time does not vary with input size, we say it's $O(1)$, which is essentially saying it varies proportionally to 1; i.e., doesn't vary at all (because 1 is constant).

Of course, 1 is not the only constant. Any number could have been used there, right? (Incidentally, I think this is related to the common mistake many CS students make, thinking "$O(2N)$" is any different from $O(N)$.)

It seems to me that 1 was a sensible choice. Still, I'm curious if there is more to the etymology there—why not $O(0)$, for example, or $O(C)$ where $C$ stands for "constant"? Is there a story there, or was it just an arbitrary choice that has never really been questioned?

• $O(0)$ is not the same as $O(1)$. $f(x)=O(0)$ means that there is some constant $c$, such that $f(x)<c\times 0$ for large enough $x$. That means $f(x)$ is negative when $x$ is big enough. But that's not what $O(1)$ means. – Untitled Sep 18 '13 at 17:29
• @Untitled I think that's an answer. – Raphael Sep 18 '13 at 18:08
• @Untitled: Ah, so I was mistaken; there is a special meaning for O(0). But the question still remains for other values besides 1. – Dan Tao Sep 18 '13 at 19:33
• @Untitled: The usual definition for O notation refers to the absolute values of the functions involved. Thus, even an all-negative function isn't O(0). – chirlu Sep 19 '13 at 13:39
• $0(1)$ requires only 1 bit, while $O(C)$, for some positive constant $C$ requires requires $\log_2 C$ bits. So using the constant $1$ may save space. - - - - (sorry, I was not going to wait till April first for this comment) – babou Feb 26 '15 at 12:05

5 Answers

"$O(1)$" is used because it is simple, clear and unambiguous. "$O(C)$" would be a poor choice of notation because in any given context, $C$ might have a specific meaning, such as the number of clauses in a CNF formula, the number of components in a graph.

• The main problem with $O(C)$ is, arguably, that (almost) nobody denotes explicitly which quantity tends to what. $O_{C \to \infty}(C)$ is not the same as $O_{n \to \infty}(C)$, but $O(1)$ is always the same. – Raphael Feb 24 '15 at 13:56

There is no reason why you can't write $O(2)$ instead. $O(1)$ can equally be expressed as $O(2)$, or $O(1/2)$ or $O(2\pi)$, etc. (Untitled explained why it can't be $O(0)$.) It's purely a matter of convention.

Others have already answered but I thought I should correct a comment by @Untitled that answers have referred to: $f(x) = O(0)$ does not imply that $f$ becomes negative close to the limit considered.

Indeed the definitions are in absolute value: $|f(x)| \leq c\cdot0$ implies $f$ is $0$ close to the limit considered.

• Actually, it is good that the comment is now an answer. Hopefully you get some upvotes too so that you can comment more :-) – Juho Feb 24 '15 at 12:22

The notation $O$ is frequently used to analyze the running time of an algorithm. It is a convenient notation because it gives a simple scale for comparing algorithms. The functions $n^k$, for $k \geqslant 0$ are part of this scale and the case $k = 0$ corresponds to the constant function $1$. So this choice is just an instance of "the simpler, the better".

You can write $O(k)$ as well, what it conveys is the fact that the asymptotic runtime is independent of the size of the input $n$, and is bound by some constant times $k$.

The Landau notation puts great emphasis on the ease of analysis. Suppose you have to compute $O(1) + O(13) + O(123)$. That can become quite messy, so instead you say $O(1)+O(1)+O(1) \in O(1)$. Again, the intuition here is there is a constant that put a bound on their sum, and is independent of the size of the input.

• No, no, no. Do not write "$O(k)$" when you mean $O(1)$. If you write "$O(k)$" to mean "bounded by a constant" in a context where $k$ already has a meaning, you've written the wrong thing: "A $k$-connected graph has at most $O(k)$ widgets" means something very different from "A $k$-connected graph has at most $O(1)$ widgets." If you write "$O(k)$" in a context where $k$ doesn't have a meaning, your reader's reaction will be "What on earth is $k$?" – David Richerby Sep 19 '13 at 17:26