Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

The interaction between big-O notation and equals signs can be confusing. We write things like $$\tag{1} 3n^2+4 = O(n^2)$$ $$\tag{2} 5n^2+7n = O(n^2)$$ But we're not allowed to conclude from these two statements that $3n^2+4=5n^2+7n$. Thus it seems that transitivity of equality fails when big-O is involved. Also, we never write things such as $$\tag{3} O(n^2)=3n^2+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(n^2)$ properly denotes the set of functions that grow at most quadratically, and that equations like $(1)$ are just conventional abbreviations for $$\tag{4} (n\mapsto 3n^2+4)\in O(n^2)$$ 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 $$\tag{5} 5 + O(n) + O(n^2)\log(O(n^3)) = O(n^2\log n)$$ 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?

share|improve this question
4  
What's wrong with (5) in terms of sets? It says "The set of functions which are of the form $5+f(n) + g(n) \log h(n)$, where $f \in O(n)$, $g \in O(n^2)$ and $h \in O(n^3)$, is a subset of $O(n^2 \log n)$." –  David Speyer Nov 27 '11 at 16:02
1  
In any case, I recall a good discussion of this in chapter 9 of Concrete Mathematics. –  David Speyer Nov 27 '11 at 16:03
    
@David, that's essentially what my interpretation produces, but you need some sort of explicit interpretation rule in order to get from $5+O(n)+O(n^2)\log(O(n^3))$ to "the set of functions which are for the form ...", and also to get from $=$ to "is a subset of$, and so forth. –  Henning Makholm Nov 27 '11 at 16:38
    
Related answer. –  Did Nov 27 '11 at 17:03
4  
Henning, the rules are clear: Landau symbols denote function classes and should be treated as such. However, many people abuse notation in order to be more succinct. As long as you can expect your audience to be clear about the meaning, go ahead. David, the problem is that many people will mess up quickly. My favorite (found in a mathematics master thesis) is $2^{O(n)} = O(2^n)$. –  Raphael Nov 27 '11 at 17:45
add comment

2 Answers 2

up vote 14 down vote accepted

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.

share|improve this answer
1  
ad bottomline: What have you read? I have come across multiple mistakes founded in misunderstandings of Landau symbols. ad personal stand: a wrong statement can not have a deeper meaning, and unclear statemens sometimes have several, contradicting ones. I prefer clarity. At the very least, every writer should clearly state somewhere how formula containing Landau notation should be read and be very careful to be correct about their use. –  Raphael Nov 27 '11 at 23:11
4  
@Raphael It's fine that you disagree with me, but let's not make it personal. (I find "What have you read?" rather distasteful.) It could just be me, but I find the notation very clear and won't hesitate to say so. And, why should every writer clearly state the meaning of the formula? There's but one way to read a formula containing a Landau notation -- it's standard and one picks it up with some experience. (And about being careful to be correct in using or reading a formula containing the asymptotic notation, I can't agree more.) –  Srivatsan Nov 27 '11 at 23:17
    
@Raphael Note. This question is not about the pitfalls one encounters in using the asymptotic notation. That is an important issue and is worthy of a separate post. This post seeks a principled way that justifies an already existing usage -- that is also, fortunately or otherwise -- common and standard. My answer is a step towards that. [I agree that the personal stand para defending the notation is a bit off-topic here, but the rest of the answer is on-topic.] –  Srivatsan Nov 27 '11 at 23:24
    
I had no intention to attack you, I was just honestly puzzled you never observed misuse. You are right that the OP asks mainly for the rules. I think, though, that every explanation of these (conventional) rules should clearly state its limitations and dangers, too. I think we are doing well here. –  Raphael Nov 28 '11 at 19:02
1  
@Rapheal Thanks for the clarification. I am on your boat w.r.t. its potential for misuse. In fact I was thinking that, when time permits, I (or someone else) should post a sister thread on the dos and don'ts of asymptotic notation. –  Srivatsan Nov 28 '11 at 19:07
show 1 more comment

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.

share|improve this answer
    
This is a very helpful answer, which I am glad to have recorded. The usual way I have seen this phrased, rather than talking about quantifiers, is that an expression containing big-O's means "the set of all functions of the form ...", where one must use fresh functions as you describe. An equality between such expressions means "is a subset of". For those who are bothered by the lack of symmetry, remember that English speakers have no trouble accepting "A robin is a bird" as valid while rejecting "A bird is a robin". See Concrete Mathematics or The Art of Computer Programming. –  David Speyer Nov 27 '11 at 16:58
4  
The most important thing that is left out by using $O$ instead of $\cal{O}$ is that every quantifier introduces a new constant. In my experience, this is the trap unwary will easily fall into. –  Raphael Nov 27 '11 at 17:48
1  
And even the slightly more wary may be tripped up by $O$ inside a sum, such as $f(x) = \sum_{k=1}^{\infty} O(x 2^{-k})$. Is this expression $O(x)$? It depends on whether the constant in the $O$ depends on $k$ or not. At this point, I suggest stating explicitly what you mean. –  David Speyer Nov 27 '11 at 18:32
    
Yes and no; if the "constant" depended on $k$, $O$ would not be appropriate at all. But even if it is independent of $k$ there does not necessarily exist one constant for a bound of the whole sum. –  Raphael Nov 27 '11 at 23:07
    
My interpretation would (so I claim) make it explicit that you have to be wary of $\sum_{k=1}^\infty O(x2^{-k})$, because the rewriting I specify would entail lifting an expression that contains $k$ out of its scope. Nonsense results. The set-of-functions algebra Srivatsan describes would, unless I'm missing something, produce the set of all possible functions for this expression -- but not be quite clear about what's going wrong. –  Henning Makholm Nov 27 '11 at 23:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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