49
$\begingroup$

People are always having trouble with "big $O$" notation when it comes to how to write it down in a mathematically correct way.

Example: you have two functions $n\mapsto f(n) = n^3$ and $n\mapsto g(n) = n^2$

Obviously $f$ is asymptotically faster than $g$. Is it $f(n) = O (g(n))$ or is it $f(n) \in O(g(n))$?

My prof says that the first one is wrong but is a very common practice, therefore it is used very offten in books. Although the second one is the right one.

Why is that so?

$\endgroup$
  • 34
    $\begingroup$ Formally, neither are. If you define $O(\cdot)$ as a set of functions (for asymptotics w.r.t. a given point), say $O(g) = \{ f : \exists N,C>0,\ \forall n\geq N\ f(n) \leq C\cdot g(n)\}$, then you would have to write $f\in O(g)$. $f(n)$ is not a function, it's a number. But most people are quite happy with the (slight) abuse of notation: $f(n) = O(g(n))$ for $f\in O(g)$, because there is no ambiguity anyway. $\endgroup$ – Clement C. Dec 20 '16 at 15:13
  • 3
    $\begingroup$ Ah, because f(n) would be a specific value when f is meant generally, is that right? $\endgroup$ – Blnpwr Dec 20 '16 at 15:14
  • 2
    $\begingroup$ Indeed. The same way that, technically, $f(x)$ is the value of the function $f$ when evaluated at the point $x$, not the function $f$ itself. $\endgroup$ – Clement C. Dec 20 '16 at 15:15
  • 2
    $\begingroup$ For this particular case, you have in fact $g(n) = o(f(n))$ or $f(n) = \omega(g(n))$ because $\lim_n \frac{f}{g} = \infty$ $\endgroup$ – Alex Dec 20 '16 at 15:48
  • 1
    $\begingroup$ For your example functions it's the other way around. $g(n)=O(f(n))$. I'm assuming we're talking about $n\to\infty$, which is hinted by the use of the letter $n$. $\endgroup$ – Meni Rosenfeld Dec 21 '16 at 9:48
63
$\begingroup$

I really like Wikipedia's note on this:

The statement “$f(x)$ is $O(g(x))$” […] is usually written as $f(x) = O(g(x))$. Some consider this to be an abuse of notation, since the use of the equals sign could be misleading as it suggests a symmetry that this statement does not have. As de Bruijn says, $O(x) = O(x^2)$ is true but $O(x^2) = O(x)$ is not. Knuth describes such statements as “one-way equalities”, since if the sides could be reversed, “we could deduce ridiculous things like $n = n^2$ from the identities $n = O(n^2)$ and $n^2 = O(n^2)$.”

For these reasons, it would be more precise to use set notation and write $f(x) \in O(g(x))$, thinking of $O(g(x))$ as the class of all functions $h(x)$ such that $|h(x)| \leq C|g(x)|$ for some constant $C$. However, the use of the equals sign is customary. Knuth pointed out that “mathematicians customarily use the $=$ sign as they use the word ‘is’ in English: Aristotle is a man, but a man isn't necessarily Aristotle.”

$\endgroup$
  • 14
    $\begingroup$ Gotta love an answer backed up by Knuth, even if it is by a quote inside a quote. $\endgroup$ – Jasper Dec 20 '16 at 17:30
  • 2
    $\begingroup$ This still isn't a complete answer. Using $f(x)$, $g(x)$, $h(x)$, $n$, $n^2$ etc. to mean functions is also abuse of notation. $\endgroup$ – JiK Dec 21 '16 at 15:07
  • 3
    $\begingroup$ @JiK you're right, but it is a common abuse of notation, and in my opinion the crux of the question regards whether to use $=$ or $\in$, not whether or not to be completely formal every time you talk about a function $\endgroup$ – TomGrubb Dec 21 '16 at 15:15
  • $\begingroup$ I don't agree with the statement would be more precise to use set notation. It implora that messure theory lenguage almost every point, cotient spaces, etc. are wrong lenguage. I think viewing big O / little o notation in this way is a bery powerful tool and os pretty precise. $\endgroup$ – Ernesto Iglesias Apr 23 '18 at 16:40
32
$\begingroup$

Using $\in$ is set-theoretically correct but inconvenient. For example, $$ \sin x = x - \frac{x^3}{3} + \mathrm O(x^5) $$ In this case $\mathrm O$ should be interpreted as there exists an $\mathrm O(x^5)$ function to make this equality valid. The $=$ notation also allows asymptotic notation to appear on both sides and do arithmetic: $$ e^x + \mathrm O(x) = \mathrm O(e^x) $$ In this case, for every $\mathrm O(x)$ function on the left, there exists an $\mathrm O(e^x)$ function on the right to make this an equality.

Warning: In this case the two sides of $=$ cannot be swapped carelessly. e.g. $\mathrm O(x) = \mathrm O(e^x)$ but $\mathrm O(e^x) \neq \mathrm O(x)$.

$\endgroup$
  • 8
    $\begingroup$ "but inconvenient" Indeed! I would go as far as saying that using it almost completely defeats the very purpose of the notation, rendering it pointless to introduce it in the first place. $\endgroup$ – quid Dec 20 '16 at 20:02
  • 5
    $\begingroup$ For what it's worth, there is a way to reconcile this. The way I think about it is that using $\mathcal O(x^5)$ here changes the abuse of notation somewhat: we're now dealing with sets of functions, so the function $x$ becomes the singleton set $\{ x \mapsto x \}$ (and likewise for $x^3 / 3$), the addition operator becomes setwise product-addition $A \oplus B = \{ x \mapsto f(x) + g(x) : f \in A, g \in B \}$, $\mathcal O(x^5)$ really is a set, and the whole statement should be read as $(x \mapsto \sin x) \in {\text{RHS}}$. Perhaps slightly inconvenient, but I don't see anything unsound. $\endgroup$ – wchargin Dec 21 '16 at 8:00
  • $\begingroup$ This reminds me of equality of multifunctions, like if we say $\cos^{-1} 1 = 2k\pi$ $\endgroup$ – GFauxPas Dec 21 '16 at 14:24
  • 1
    $\begingroup$ @wchargin Using $O(x^5)$ does not automatically mean we are dealing with sets of functions. All that the writer means is that they're dealing with a specific quantity which satisfies the definition of being $O(x^5)$. The purpose of notation is to communicate what a mathematician is thinking. Introducing sets of functions—frankly, no one cares about the set of all functions that are $O(x^5)$ and it's an uninteresting set; we only care that the particular function we're working with is $O(x^5)$—is backwards, saying we should change our thinking to fit (someone's narrow idea of) $=$ notation. $\endgroup$ – ShreevatsaR Dec 21 '16 at 20:42
  • $\begingroup$ @SheevastaR ¡¡¡Of course we care for the set $O(g)$!!! if you don't is a problem you have. Read the answer you are commenting and you will notice how important it is. $\endgroup$ – Ernesto Iglesias Apr 23 '18 at 16:49
10
$\begingroup$

$O(g(x))$ is a class of functions - think of it as a "property" functions can have. By the literal interpretation of the equals sign, "$f(x) = O(g(x))$" should be interpreted as "$f$ is literally equal to a certain class of functions." But functions and classes of functions are different sorts of things - even if this was what we meant to say, it's like saying that one particular apple is equal to a basket of apples. But what we mean when we say "$f(x) = O(g(x))$" is that $f$ belongs to the class of functions $O(g(x))$ - so, $f(x) \in O(g(x))$.

The reason we use $=$ instead of $\in$ is because, given the particular uses of big-$O$ notation (and little-$o$ notation, if you're familiar with that) $=$ is massively more convenient. We say things like $x^3 + O(x) = O(x^3)$, for example; we don't mean that $O(x)$ is an object that can actually be added to $x^3$, or that when that addition is done we actually get the class of functions $O(x^3)$, we just mean that for any function $f \in O(x)$, the function $x^3 + f(x)$ is a member of $O(x^3)$. But if I wanted to write that out in more standard notation, I'd have to say something like $\{x^3 + f(x) \mid f(x) \in O(x)\} \subseteq O(x^3)$. This is inconvenient to write and difficult to read, so we prefer the "slicker" notation $x^3 + O(x) = O(x^3)$.

However, I'm not sure I would say that sentences like $f(x) = O(g(x))$ are wrong. By convention, they're perfectly right - it's just that when an expression includes $O$ (or $o$), $=$ does not mean what it usually means. That's okay.

$\endgroup$
  • $\begingroup$ I think there must be someone that had invented a convenient way to just say $x^3 + O(x) = O(x^3)$, and at the same time, the symbols are entirely rigorous. $\endgroup$ – Eric Dec 20 '16 at 16:29
  • 6
    $\begingroup$ @Eric Well, $x^3 + O(x) = O(x^3)$ is an entirely rigorous and convenient way to say that. It just doesn't look rigorous if you don't know the definition of "$=$" in the context of $O$. Since everyone in the field understands this notation, no one's particularly motivated to find a new way of writing it that won't confuse outsiders. $\endgroup$ – Reese Dec 20 '16 at 16:34
  • $\begingroup$ @Reese If you treat $O(x)$ as a set, then $x^3 + O(x) \subseteq O(x^3)$ is rigorous without domain-specific $=$ sign. $\endgroup$ – heinrich5991 Dec 21 '16 at 1:02
  • 4
    $\begingroup$ @heinrich5991 But that requires domain-specific $+$. $\endgroup$ – Reese Dec 21 '16 at 1:34
  • 1
    $\begingroup$ @heinrich5991 Oh, absolutely, it's common. But so is using $=$ for $O$ and $o$. My point is that it's still not transparent to first learners. $\endgroup$ – Reese Dec 22 '16 at 17:29
4
$\begingroup$

I'll try to clarify wchargin comment.

If you are familiar with Group theory you should not find the $=$ sign awkward. Class of equivalence and quotient spaces usually use the sum notation for doing that.

e.g., $\mathbb{R}/\mathbb{Z}$ elements are usually written as $a+\mathbb{Z}$.

The problem is that big $O$ notation makes implicit use of that, i.e. in the class of $$O(g)=\lbrace f:\exists M,C>0, \forall x_0\geq M: f(x_0)\leq Cg(x_0) \rbrace,$$ as exposed by Clement C.

In this way, $$f=O(g)$$ Means $$f+O(g)=0+O(g)$$ And that is to say than $f\in O(g)$.

$\endgroup$
3
$\begingroup$

Regarding $=$ being more useful/convenient than $\in$ because of allowing things like $x^3 + O(x) = O(x^3)$, it seems like for that you could use $x^3 + O(x) \subseteq O(x^3)$. This seems more precise to me, because it would mean "every element of the set $x^3 + O(x)$ is an element of the set $O(x^3)$." which is, I think, exactly what one wants to say. (where $g+A:=\{g+f:f\in A\}$ and when $g$ is a function and $A$ is a set of functions, and similarly for similar situations.)

Making the statement with subset is mentioned by Reese's answer, but I think that defining the sum of a function and a set of functions, and also the sum of sets of functions, in the straightforward way removes the inconveniences of saying things like $\{x^3+f(x)∣f∈O(x)\}\subseteq O(x^3)$. (Defining things similarly with multiplication, and application of functions in general.)

When things are defined this way, it should become as simple as using $\in$ instead of $=$ when there is a single function on the left, and using $\subseteq$ instead of $=$ when there is a set of functions on the left, and it seems more precise.

$\endgroup$
  • 1
    $\begingroup$ No, set-theoretic inclusion is not "exactly what one wants to say". The purpose of notation is to aid communication, and it is meant to fit our way of thinking. It is misguided to insist that one should change one's (very productive) way of thinking just to fit some notation or formalism. When an analyst writes $\sin x = x - \frac{x^3}{3} + \mathrm O(x^5)$ they are literally thinking that $\sin x$ is equal to $x$ minus $\frac{x^3}{3}$ plus some function that is $\mathrm O(x^5)$ — they are thinking of equality, not set inclusion, so the notation reflects that. $\endgroup$ – ShreevatsaR Dec 21 '16 at 18:54
  • $\begingroup$ Ok, I should probably defer to you here. But isn't saying that $sin(x)$ is equal to $x - \frac{x^3}{3}$ plus some function that is $O(x^5)$ the same thing as saying that $sin(x)$ is an element of the set of functions which are of the form $x - \frac{x^3}{3}$ plus some function that is $O(x^5)$? $\endgroup$ – drocta Dec 21 '16 at 20:31
  • $\begingroup$ Well, is saying "the sky is blue" the same thing as saying "the sky is an element of the set of things that are blue"? In some sense yes, and in another sense no. (It may be logically equivalent, but the speaker may not have even considered, or care about, the set of all things that are blue.) One can also say "the sky satisfies the property of being blue", or even "blueness inheres in the sky". There can be many ways to formalize a statement, and the most fruitful ones are often the one that closest match what the human is thinking, rather than what fits cleanest with other formalisms. $\endgroup$ – ShreevatsaR Dec 21 '16 at 20:45
  • $\begingroup$ (sorry, I hit enter by mistake. First time using SE comments.) Your point about the purpose being for communication seems like something I failed to consider. But $\in$ being like "has property" and $\subseteq$ being like "all things with property on the left have the property on the right$, seem like they capture the $\forall$ or $\exists$ in what is being said with "there exists a function of the form $x-x^3/3+O(x^5)$ which is $sine(x)$, and "for all functions of the form <blah>, there is a function of the form <bleh> such that they are equal". But maybe it's not nice enough to justify sets? $\endgroup$ – drocta Dec 21 '16 at 20:57
2
$\begingroup$

Here is my five pennies worth: If we see a statement of the form $$f(x)=g(x)+O\bigl(p(x)\bigr)\qquad(x\to\xi)$$ then for each $x$ the exact value of the term $O\bigl(p(x)\bigr)$ is defined by this very equation: it is $:=f(x)-g(x)$. In addition we are told that there is a constant $C>0$ such that for all $x$ in a suitable punctured neighborhood of $\xi$ this difference is $\leq C\bigl|p(x)\bigr|$.

$\endgroup$

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.