4
$\begingroup$

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?

$\endgroup$
  • 10
    $\begingroup$ $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. $\endgroup$ – Untitled Sep 18 '13 at 17:29
  • 2
    $\begingroup$ @Untitled I think that's an answer. $\endgroup$ – Raphael Sep 18 '13 at 18:08
  • $\begingroup$ @Untitled: Ah, so I was mistaken; there is a special meaning for O(0). But the question still remains for other values besides 1. $\endgroup$ – Dan Tao Sep 18 '13 at 19:33
  • 1
    $\begingroup$ @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). $\endgroup$ – chirlu Sep 19 '13 at 13:39
  • $\begingroup$ $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) $\endgroup$ – babou Feb 26 '15 at 12:05
12
$\begingroup$

"$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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Feb 24 '15 at 13:56
10
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

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

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".

$\endgroup$
-1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$?" $\endgroup$ – David Richerby Sep 19 '13 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.