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

This question is about asymptotic notation in general. For simplicity I will use examples about big-O notation for function growth as n (seen in algorithmic complexity), but the issues that arise are the same for things like Ω and Θ growth as n, or for little-o as x0 (often seen in analysis), or any other combination.

The interaction between big-O notation and equals signs can be confusing. We write things like
3n2+4=O(n2)
5n2+7n=O(n2)
But we’re not allowed to conclude from these two statements that 3n2+4=5n2+7n. Thus it seems that transitivity of equality fails when big-O is involved. Also, we never write things such as O(n2)=3n2+4,
so apparently commutativity is also at risk.

Many textbooks point this out and declare, with varying degrees of indignation, that notations such as (1) and (2) constitute an “abuse of notation” that students are just going to have to get used to. Very well, but then what are the rules that govern this abuse? Mathematicians seem to be able to communicate using it, so it can’t be completely random.

One simple way out is to define that the notation O(n2) properly denotes the set of functions that grow at most quadratically, and that equations like (1) are just conventional abbreviations for
(n3n2+4)O(n2)
Some authors even insist that writing (1) is plain wrong, and that (4) is the only correct way to express the estimate.

However, other authors blithely write things like
5+O(n)+O(n2)log(O(n3))=O(n2logn)
which does not seem to be easily interpretable in terms of sets of functions.

The question: How can we assign meaning to such statements in a principled way such that (1), (2) and (4) are true but (3) is not?

Answer

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, +,×,,÷,exp,log) and asymptotic notations {O,o,Ω,ω,Θ} 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:
E1E2:={f(n)g(n):f(n)E1,g(n)=E2},{+,×,,÷};Ψ(E):={Ψ(f(n)):f(n)E},Ψ{exp,log}.
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):=f(n)EO(f(n)).

These rules are not complete; one needs to append the appropriate base cases when E, E1 and E2 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(n2)log(O(n3)) stands for the set
{5+f(n)+g(n)logh(n) : f(n)O(n),g(n)O(n2),h(n)O(n3)}.
Similarly we can interpret the expression like O(2n2+O(n)) by applying the O() rule twice.


Rules for Interpreting the Equals sign. When one asserts that E1=E2 where E1 and E2 are sets represented by expressions like the above, one should always interpret it to mean that E1E2. E.g., 5+O(n)+O(n2)log(O(n3)) = O(n2logn) is really a shorthand for 5+O(n)+O(n2)log(O(n3))  O(n2logn).

In addition, there is the case f(n)=E; e.g., n=O(n2). 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)E (because f(n)E{f(n)}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:
E1=E2(??)E2=E1.
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(n2) whereas n2?=O(n) is false. This is for the same reason that set inclusion is not.

  • However it is transitive; i.e., if E1=E2 and E2=E3, then E1=E3. 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 or as appropriate.

Attribution
Source : Link , Question Author : hmakholm left over Monica , Answer Author : Srivatsan

Leave a Comment