The relation of $O$- and $\Omega$-symbols and an unexpected absolute sign in the definiton of $O$.

Question

In the article Big Omicron and the big omega and big theta D. Knuth defines on p.19 \begin{align*} O(f(n)) & := \{ g(n) \mid \exists C > 0 \exists n_0 > 0 \forall n \ge n_0 : |g(n)| \le Cf(n) \} \\ \Omega(f(n) & := \{ g(n) \mid \exists C 0 \exists n_0 > 0 \forall n \ge n_0 : g(n) \ge Cf(n) \}. \end{align*} And the whole article centers around the idea to define $\Omega(f(n))$ as a lower bound notation contrary to $O(f(n))$. On wikipedia it is written $$ f(n) \in \Omega(g(n)) \Leftrightarrow g(n) \in O(f(n)). $$

But what puzzles me is the absolute sign in the definition of $O(f(n))$. By this the above symmetry does not hold? So why is there an absolute sign? And then shouldn't there be an absolute sign around $f(n)$ too?

The author itself mentions on page 21:

[...] Note that there is a slight lack of symmetry in the above definitions of $O$, $\Omega$, and $\Theta$, since absolute value signs are used in $g(n)$ only in the case of $O$. This is not really an anomaly, since $O$ refers to a neighborhood of zero while $\Omega$ refers to a neighborhood of infinity. [...]

Guess it is related to my question, but I totally do not understand this paragraph, both symbols say something about the behaviour for very large arguments, hence both refer to a neighborhood of infinity?? So what does the author has in mind if he says $O$ refers to a neighborhood of zero?

So I hope someone could clarify the relations. Why is there an absolute sign written in one definition, and not in the other? And why is there no absolute sign around both $g(n)$ and $f(n)$? And how does the equivalence from wikipedia holds? As I see it, it does not holds in general, just for positive functions? And what does the author tries to say with the above cited paragraph?

Answer 1

We start with three big-O and big-$\Omega$ definitions stated by D.E. Knuth at three different points of time.

BIG OMICRON AND BIG OMEGA AND BIG THETA (D.E. Knuth, 1976)

• $O(f(n))$ denotes the set of all $g(n)$ such that there exist positive constants $C$ and $n_0$ with $|g(n)|\leq Cf(n)$ for all $n\geq n_0$.

• $\Omega$ denotes the set of all $g(n)$ such that there exist positive constants $C$ and $n_0$ with $g(n)\geq Cf(n)$ for all $n\geq n_0$.

Concrete Mathematics (R.L.Graham, D.E. Knuth, O. Patashnik, 1989)

• The $O$-notation is governed by its environment, by constraints on the variables involved. These constraints are often specfied by a limiting relation. For example, we might say that \begin{align*} |f(n)|\leq C|g(n)|\qquad\text{whenever }n\geq n_0. \end{align*} The values of $C$ and $n_0$ might be different for each $O$, but they do not depened on $n$. Similarly, the notation \begin{align*} f(x)=O(g(x))\qquad\text{as }x\to 0 \end{align*} means that there exist two constants $C$ and $\varepsilon$ such that \begin{align*} |f(x)|\leq C|g(x)|\qquad\text{whenever }x\leq \varepsilon. \end{align*} There's another notation, Big Omega, for lower bounds: \begin{align*} f(n)=\Omega(g(n))\Longleftrightarrow|f(n)|\geq C|g(n)|\qquad \text{for some }C>0. \end{align*}

  (and later on we can read:)

  We have $f(n)=\Omega(g(n))$ if and only if $g(n)=O(f(n))$.

Mathematics for the Analysis of Algorithms (D.E. Greene, D.E. Knuth, 1994)

• We say that $f(n)=O(g(n))$ as $n\to\infty$ if there exist integers $N$ and $K$ such that $|f(n)|\leq K|g(n)|$ for all $n\geq N$.

• In a similar vein, $f(n)=\Omega(g(n))$ as $n\to\infty$ if there exist integers $N$ and $K$ such that $|f(n)|\geq K|g(n)|$ for all $n\geq N$.

Comment: We see three definitions stated by D.E. Knuth whereby the second and third are more or less the same and symmetrically stated with respect to the usage of absolute value sign, while the first is stated slightly differently.

Possible reasons why the first definition is slightly different than the other two:

• Context: When given the first definition the author had the relevant functions in mind. These are the functions which are positive for all sufficiently large $n$ and maybe he didn't explicitely state it, since it might have been obvious from his point of view.

• Common usage (at that time): When doing the historical recherche on asymptotic notation one of the main sources for Knuth was the work of G.H. Hardy. In the book Divergent Series which was published in 1948, Hardy introduces the Big-O notation as follows (p.XVI).

  If $\Phi>0$, then \begin{align*} `f=O(\Phi)'\qquad\text{means}\qquad `|f|<H\Phi' \end{align*}

  Hardy explicitly states that $\Phi>0$, and provides a definition which corresponds to the first definition of Knuth. Maybe it has been more common to state it this way at that time.

• Psychological considerations: This is admittedly highly speculative, but one the main reasons of the 1976 paper was to convince the mathematical community of the usefulness of the asymptotic notation. In order to do so he has also changed/adapted the definition of big-$\Omega$. To not scare the community by introducing too many changes he might have been decided to use the big-O definition in the meaning given by Hardy.

Note: It should be noted, that Knuth dedicates in Concrete Mathematics a whole chapter (chapter 9: Asymptotics) to the asymptotic notation and provides a thorough introduction into it. I would rather take this book as the most relevant from Knuth when looking for an appropriate definition. On the other hand Knuths first paper is of highest importancce when we are considering the historical aspects of asymptotic notation and the spread of these ideas into the mathematical community.

On the equivalence \begin{align*} f(n) \in \Omega(g(n)) \Longleftrightarrow g(n) \in O(f(n))\tag{1} \end{align*}

I think the statement in Wikipedia is misleading, since (1) is not stated in Knuth's first paper. But it is stated in Knuth's Concrete Mathematics (see the definitions above) where the definition is symmetrical with respect to the absolute value sign and (1) clearly holds.

From my point of view the Wikipage needs to be updated and should refer to Knuth's definition stated in Concrete Mathematics and the first paper should have been pointed out with respect to its historical importance for spreading the ideas in the mathematical community.

On the seemingly anomaly of different usage of the absolute value signs.

I also don't see the deeper reason why Knuth gives this explanation. But he considers the extended real numbers $\mathbb{R}\cup\{\pm\infty\}$ with the usual topology.

A neighborhood of zero is defined to contain an open ball containing zero. The inequality $|g(n)|\leq C f(n)$ indicates this, since the interval $(-C f(n), Cf(n))$ is a neighborhood of zero.

On the other hand a neighborhood of $\infty$ is defined to contain an open ball containing $\infty$ and the inequality $g(n)\geq C f(n)$ indicates this, since $(C f(n),\infty)$ is a neighborhood of infinity.