What are the rules for equals signs with big-O and little-o?

Solution 1:

My take on this notation agrees with David Speyer's comment. As Henning's answer notes, our answers are just different ways to look at the same thing. Often I resort to rules similar to his as the operative definition, but I find the my approach easier to motivate.

We proceed in two steps: (a.) understanding an expression involving asymptotic notation, and (b.) understanding the use of the equals sign in this notation.

Rule for Interpreting Expressions. Every (well-formed) expression involving standard functions and operations (e..g, ${ +, \times, -, \div, \exp, \log }$) and asymptotic notations $\{ O, o, \Omega, \omega, \Theta\}$ corresponds to a set of functions. [For simplicity, we will restrict ourselves to only the $O$ notation.] This set is built recursively exactly as one would expect: $$ \begin{align*} E_1 \circ E_2 &:= \{ f(n) \circ g(n) \quad : \quad f(n) \in E_1, g(n) = E_2 \}, \quad \circ \in \{ +, \times, -, \div \}; \\ \Psi (E) &:= \{ \Psi(f(n)) \quad : \quad f(n) \in E \}, \quad \Psi \in \{ \exp, \log \}. \\ \end{align*} $$ This interpretation of expressions is perfectly natural; it's analogous to the Minkowski sum of two sets, extended for more general operations. We can even enrich this with a slightly more involved rule for $O$:

$$ O(E) := \bigcup_{f(n) \in E} O(f(n)). $$

These rules are not complete; one needs to append the appropriate base cases when $E$, $E_1$ and $E_2$ are single functions rather than a set of functions. The most interesting base case is the expression $O(f(n))$ which is defined exactly as in the post. As a final point, we can agree to identity a single function $f(n)$ with the set $\{ f(n) \}$; this turns out to be very convenient in practice.

For example, an expression of the form $5 + O(n) + O(n^2)\log(O(n^3))$ stands for the set $$ \{ 5 + f(n) + g(n) \log h(n) \ : \ f(n) \in O(n), \quad g(n) \in O(n^2), \quad h(n) \in O(n^3) \}. $$ Similarly we can interpret the expression like $O(2^{n^2 + O(n)})$ by applying the $O(\cdot)$ rule twice.

Rules for Interpreting the Equals sign. When one asserts that $E_1 = E_2$ where $E_1$ and $E_2$ are sets represented by expressions like the above, one should always interpret it to mean that $E_1 \subseteq E_2$. E.g., $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{=} \ O(n^2\log n)$$ is really a shorthand for $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{\subseteq} \ O(n^2\log n) .$$

In addition, there is the case $f(n) = E$; e.g., $n = O(n^2)$. In this case, we can identity the function $f(n)$ with the set $\{ f(n) \}$ and apply the above interpretation. This tells us that $f(n) = E$ is the same as saying $f(n) \in E$ (because $f(n) \in E \iff \lbrace f(n) \rbrace \subseteq E$).

This is arguably unnatural since this clashes starkly with the standard interpretation of the equals sign as (set) equality. In fact, this is an inherent difficulty since we would expect any reasonable definition of equality to be symmetric: $$ E_1 = E_2 \quad \stackrel{\color{Red}{(??)}}{\implies} \quad E_2 = E_1. $$ However, as we all know, this is seldom true with the asymptotic notation. Thus the only way out seems to be to override the intuitive notion of equality in favor of a less natural one. [At this stage, it is worth pointing out that Henning's rules also resorts to redefining the equals sign suitably.]

A sample of properties. Many commonly used rules for manipulating asymptotic notation follow directly from the above interpretation. As a case study, I consider some of the properties already studied by Henning in his answer:

• "Local scope" or Change of meaning. For example, In $O(n) + O(n) = O(n)$, you can substitute distinct functions $f(n)$, $g(n)$ and $h(n)$. The definition of "$+$" in the set-of-functions interpretation is clearly based on this idea.

• The asymptotic notation is not symmetric. E.g., $O(n) = O(n^2)$ whereas $n^2 \stackrel{\color{Red}{?}}{=} O(n)$ is false. This is for the same reason that set inclusion is not.

• However it is transitive; i.e., if $E_1 = E_2$ and $E_2 = E_3$, then $E_1 = E_3$. This simply follows from the transitivity of set inclusion.

Final words. One main complaint against the asymptotic notation seems to be that it is usually not symmetric as is implied by the equals sign. This is legitimate, but in this case, the real issue is with the abuse of equals sign, rather than the functions-as-sets idea. In fact, as far as I remember, I am yet to come across a single use of the asymptotic notation that is technically wrong even after one mentally replaces the equals sign with either $\in$ or $\subseteq$ as appropriate.

Solution 2:

I have never seen the following rule written down in so many words, but it seems to match how the notation is being used in practice. (It is formally equivalent to the interpretation in Srivatsan's answer, in the sense that whenever both rules assign a meaning to an equation, the two meanings agree. I hold that my way of looking at it is more intuitive, but anyone's mileage may of course vary here).

I'm going to need the sets-of-functions interpretation of $O(f(n))$ as a base concept. In order to disambiguate it from the $O(f(n))$ that one can do arithmetic on, I will write if with a script $\mathcal{O}$, such that, for example, $$\mathcal{O}_{n\to\infty}(f(n)) = \Big\{g:\mathbb N\to\mathbb R \;\Big|\; \exists N,C\in \mathbb N. \forall n>N. \big[C(f(n))>g(n)\big]\Big\}$$ As in the question I will let the $n\to\infty$ subscript be implicit.

Rule: Whenever you see an equation $t=u$ where $t$ or $u$ contain one or more $O(\cdots)$, you're supposed to mentally do the following expansion:

• Replace each textual occurrence of $O(\cdots)$ with $\phi(n)$ where $\phi$ is a fresh function letter that ranges over $\mathcal O(\cdots)$. Different occurences of $O(\cdots)$ in the formula should get separate function letters, even if the "$\cdots$" are the same.
• Every fresh $\phi$ that arises from an $O(\cdots)$ on the left side of the equals sign should be universally quantified.
• Every fresh $\phi$ that arises from an $O(\cdots)$ on the right side of the equals sign should be existentially quantified.
• The universal quantifiers on $\phi$s come before the existential ones.
• The variable $n$ that tends to a limit should be universally quantified after all of the quantifiers on $\phi$s.

Some examples:

• The simple case. $3n^2+4 = O(n^2)$ means $$ \exists \psi\in\mathcal O(n^2).\forall n.\bigl[3n^2+4=\psi(n)\bigr]$$ Since there is exactly one function $\psi$ that $\forall n.\bigl[3n^2+4=\psi(n)\bigr]$, this just says that $(n\mapsto 3n^2+4)\in\mathcal O(n^2)$, so my rule is compatible with the "simple" meaning presented by textbooks.

• The complex equation from the question, $$ 5 + O(n) + O(n^2)\log(O(n^3)) = O(n^2\log n)$$ means $$\begin{align} &\forall \phi_0\in\mathcal O(n). \forall \phi_1\in\mathcal O(n^2). \forall \phi_2\in\mathcal O(n^3). \exists \psi\in\mathcal O(n^2\log n). \\& \forall n. \big[ 5+\phi_0(n)+\phi_1(n)\log(\phi_2(n)) = \psi(n)\big] \end{align}$$ which shows how the customary notation is a useful abbreviation.

• Stepwise rewriting. We can rewrite part of an expression to say $$O(n^2)+5n = O(n^2)+O(n)$$ which unfolds to $$\forall \phi\in\mathcal O(n^2). \exists \psi\in\mathcal O(n^2). \exists \xi\in\mathcal O(n). \forall n.\bigl[\phi(n)+5n=\psi(n)+\xi(n)\bigr]$$

• Change of meaning. $O(n)+5=O(n)$ means $$ \forall \phi\in\mathcal O(n). \exists \psi\in\mathcal O(n). \forall n.\bigl[\phi(n)+5=\psi(n)] $$ showing that different occurrences of $O(n)$ are allowed to mean different things.

• Transitivity of equality. If the translations of $t=u$ and $u=v$ are both true, then the translation of $t=v$ is also true (even though big-O's in $u$ are translated to differently quantified functions in the two original equations). Thus, a multi-step calculation such as $$ O(n^2) + 5n = O(n^2) + O(n) = O(n^2)$$ is justified.

On the other hand, equations between asymptotic expressions are not symmetric, because $O(n)=O(n^2)$ is true, but $O(n^2)=O(n)$ is not.