1
$\begingroup$

I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant time, in essence, a non-zero constant time. Is there a broad acceptance that a function converging to zero belongs to $o(1)$ and not to $O(1)$?

$\endgroup$
9
$\begingroup$

$O(1)$ does not represent time. It represents a class of functions, which could be used to measure time, space or literally anything else.

$f(x)\in O(1)$ if, and only if, there is a constant $c$ such that $f(x)<c$ for all large enough $x$. There's no requirement that $f$ must be eventually non-zero. $f(x)\in o(1)$ if, and only if, $\lim_{x\to\infty} f(x) = 0$ so, in particular, for all large enough $x$, $f(x)<1$. Therefore, $f(x)\in O(1)$.

$\endgroup$
  • $\begingroup$ According to the wikipedia article, $\: \hspace{.045 in}f(x) < c \:$ should be replaced with $\:\big|\hspace{.045 in}f(x)\big| < c \;$. $\hspace{1.63 in}$ $\endgroup$ – user12859 Mar 8 '14 at 22:28
  • $\begingroup$ @RickyDemer Yes; I'm assuming non-negative functions $\endgroup$ – David Richerby Mar 9 '14 at 15:47
  • $\begingroup$ The $O$ notation is not just used as $x \to \infty$. For instance, one can say $\sin x = x + O(x^3)$ (here $x \to 0$). Usually it is clear from the context. $\endgroup$ – Aryabhata Mar 12 '14 at 23:59
  • $\begingroup$ @Aryabhata True but I don't think I've ever seen it used that way in computer science, which is the subject here. (Perhaps it's used that way in numerical analysis.) $\endgroup$ – David Richerby Mar 13 '14 at 0:09
-2
$\begingroup$

I'm going to try to answer a slightly different question than you asked, namely, what the difference is between big-oh and little-oh, and how can you build some good intuition about both of them. If you know that, then the answer to your question is obvious.

I'm also going to ignore absolute values here for the sake of simplicity.

Here's a good way to visualise the difference between big-oh and little-oh. This was never explained to me in this way; I came up with this myself. I hope this helps you, too.

  • A function $f(x)$ is $O(g(x))$ if there exists a constant $c>0$ such that there exists a number $x_0$ such that $\forall x>x_0, f(x) \le cg(x)$.

  • A function $f(x)$ is $o(g(x))$ if for all constants $c>0$ there exists a number $x_0$ such that $\forall x>x_0, f(x) \le cg(x)$.

So the difference between big-oh and little-oh is that big-oh is "there exists a constant $c$", and little-oh is "for all constants $c$".

It should be clear from this alone that if $f(x)$ is $o(g(x))$ then it is also $O(g(x))$. However, there's a wider point here which it's helpful to emphasise.

Informally, $f(x) = O(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, and the constant is chosen for you. If this measures time, then the constant may be a complex interplay between the CPU designers, the laws of physics, how loaded your machine is, and so on. The point is, it's within a constant factor, and the constant factor is not under your control.

However, $f(x) = o(g(x))$ means that $f(x)$ is eventually within a constant factor of $g(x)$, but you get to pick the constant yourself, and it can be as small as you like. To rub the point in, we often name the constant $\varepsilon$ instead of $c$, because epsilon carries the connotation of "arbitrarily small".

Please let that point sink in before you read on.

Little-oh notation is far more commonly used in space analysis than time analysis, because in time analysis, we typically care about "wall time" (i.e. the time according to a clock on the wall), which invariably changes when you run the same algorithm on a new computer. However, in space analysis, we care about bits, or gigabytes, or something like that. A bit may be physically smaller when a new RAM chip or hard disk gets released, but it's not logically smaller. A bit always can only store one bit of information at the most.

So suppose that you are designing a data structure which information theory states must use at least $f(n)$ bits (say, if you're storing $n$ things in it).

  • A data structure which uses $f(n) + O(1)$ bits is called implicit.
  • A data structure which uses $f(n) + O(f(n)) = \left( 1 + O(1) \right) f(n)$ bits is called compact.
  • A data structure which uses $f(n) + o(f(n)) = \left( 1 + o(1) \right) f(n)$ bits is called succinct.

Informally, a compact data structure has constant relative overhead. This might mean 1%, 5%, or 10 times. That last one might not be as useful as 1% overhead, but still. The point is that the relative overhead (compared to a theoretically perfect solution) is a constant.

A succinct data structure, on the other hand, has a relative overhead which is eventually insignificant.

It should be clear from the above definitions that a data structure that is implicit is automatically succinct, and a data structure that is succinct is automatically compact.

$\endgroup$
  • 2
    $\begingroup$ The statements about $f(x)$ being "eventually within a constant factor of $g(x)$" are wrong. $f(x)$ can stay below $g(x)$ arbitrarily far. $\endgroup$ – FrankW Mar 10 '14 at 5:53
  • $\begingroup$ Adding to @FrankW's comment, consider $2^x$ and $3^x$. If two functions do get to being "eventually within a constant factor" of each other, they are in the same $\Theta$ (by definition). $\endgroup$ – Raphael Mar 10 '14 at 9:05
  • $\begingroup$ Sorry, maybe I'm just being dense here, but I don't understand the problem. Are we using different senses of the word "within"? $\endgroup$ – Pseudonym Mar 11 '14 at 6:42
  • $\begingroup$ Nope, I'm still not getting where you think my answer is wrong. Could the problem mean the word "eventually"? I meant it to mean that if you think of $x$ as increasing, then once $x$ passes some threshold, it will always be "within" after that. $\endgroup$ – Pseudonym Mar 12 '14 at 22:20
  • 2
    $\begingroup$ @Pseudonym "$f(x)$ is within a constant factor of $g(x)$" means that there is a constant $k$ such that $g(x)/k\leq f(x)\leq kg(x)$. It does not mean merely that there is a constant $k$ such that $f(x)$ is within (i.e., a member of) the interval $[0, kg(x)]$. (For clarity, I've omitted "for large enough $x$" and the possibility that $f$ or $g$ might be negative.) $\endgroup$ – David Richerby Mar 13 '14 at 0:01

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.