3
$\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?

Improve this question
$\endgroup$
5
  • 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, 2013 at 17:29
  • 2
    $\begingroup$ @Untitled I think that's an answer. $\endgroup$
    – Raphael
    Sep 18, 2013 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, 2013 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, 2013 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, 2015 at 12:05

5 Answers 5

Reset to default
11
$\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.

Improve this answer
$\endgroup$
1
  • 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, 2015 at 13:56
9
$\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.

Improve this answer
$\endgroup$
0
5
$\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.

Improve this answer
$\endgroup$
1
  • $\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, 2015 at 12:22
1
$\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".

Improve this answer
$\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.

Improve this answer
$\endgroup$
1
  • 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, 2013 at 17:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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