Big-O and little-o

fedja

As grobber once said "I don't really know why I'm posting this, probably just wanted to post something" Razz

. I have a colleague (a very fine mathematician, by the way), who insists that the way the $o()$ and $O()$ notation is currently used is nothing but an abuse of mathematical language. His argument is that $=$ should always be an equivalence relation and $\sin x = O(1)$ and $1 = O(1)$ imply neither $O(1) = \sin x$ , nor $\sin x = 1$ . Besides, the same symbol $O(x)$ means a lot of different things. The formally correct approach to the big and little O notation, in his opinion, should be the following. Given a positive $g$ defined in a punctured neighborhood of $x_0$ , denote by $O_{x_0}(g)$ the class of all functions $f$ such that the ratio $f/g$ is bounded in some punctured neighbourhood of $x_0$ . This is a perfectly meaningful mathematical object with unique meaning. Now, instead of writing $f(x) = O(g(x))$ as $x\to x_0$ , write $f\in O_{x_0}(g)$ . If you understand the arithmetic operations over classes of functions in the sense of Minkowski, i.e., $A*B = \{f*g: f\in A,g\in B\}$ where $*$ is any of the four arithmetic operations, then you can elaborate upon this idea and instead of writing $1 + \sin x = 1 + O(|x|) = 1 + o(1)$ as $x\to 0$ , write the formally correct $1 + \sin x\in 1 + O_0(|x|)\subset 1 + o_0(1)$ . And so on, and so forth. I find his logic irrefutable but I do not think he has a big chance to win his crusade Smile

**Posted:** Wed Oct 24, 2007 6:51 pm

Ravi B

Does your colleague also object to the $\pm$ operator as used in say the quadratic formula? Because we can derive similar contradictions from it. For example, from the equations $1 = \pm 1$ and $-1 = \pm 1$ , we can derive $1 = -1$ .

**Posted:** Wed Oct 24, 2007 7:20 pm

_________________
Check out the Math Prize for Girls!

fedja

Yes, of course. He doesn't like that bit either (or writing a chain of inequalities in which all constants are denoted by the same letter $C$ Very Happy

**Posted:** Wed Oct 24, 2007 7:26 pm

Kent Merryfield

**Posted:** Wed Oct 24, 2007 8:54 pm

fedja

Well, as a matter of fact, when I think about "hard analysis" problems, I hardly use any notation at all. Rather I go around and mumble something like "you can represent the ratio of the derivative of a polynomial to itself as the Cauchy integral over the roots; the Cauchy integral satisfies the weak type estimate; you cannot add weak type estimates but you can safely multiply them, so if I do this trick again and again, I'll write every polynomial of order $n$ as a product of a monomial and $n - 1$ Cauchy integrals, which gives me the Turan lemma for an arbitrary set instead of an interval" (of course, this is the final refined product, the actual thoughts are much more garbled, repetitive,and so on). Once I need to check an estimate for myself, I can easily write $2x + 3x = (2 + 3 = 5) = 5x\ - 10\ge 100$ if $x > 1000$ and I'm not going to apologize to anybody for that because I'm writing for myself and only I can misunderstand what I'm writing. On the other hand, when writing the proof down, especially for publicaiton, one should think of notation quite a bit to be sure that no misunderstanding will be possible. It is conventional to say "by $C$ , we shall denote an arbitrary constant that may change from one place to another" in the beginning of the paper, which is, if not an apology, than an explanation. One can use or abuse the notation as much as he wants for himself, but one has to stick to some standards when trying to communicate the message to others. There are a few "universal rules" like "don't use the same letter for 2 different things", etc. that would be firmly insisted upon by every referee and editor in all cases except the few listed above where the common usage doesn't comply with these rules. Now there are 3 kinds of people: the first will say in this situation "down with the rules", the second "stop the common usage", and the third "let us slightly adjust the common usage to make it comply with the rules". What he proposes is a very slight modification of the current notation: $\in$ instead of $=$ , which puts everything in its place. As I said, I do not see any convincing argument for refuting the proposal except "I have always done it the way I do and I'll continue it no matter what you say because it is convenient for me and helps me solve problems". But that is very close to a phrase some Fermatist may put forward in defence of his "unconventional mathematics" that allowed him to give a one page proof of FLT.

**Posted:** Thu Oct 25, 2007 3:56 am

Ravi B

Suppose we are trying to write an indefinite integral like
$\int x \, dx = \frac {1}{2} x^2 + C.$
How would we write it more properly?

By the way, in the computer science community, about 20 years ago, Giles Brassard made the same plea when using Big-Oh notation to use $\in$ or $\subseteq$ instead of $=$ . Here is a link to his article:
http://portal.acm.org/citation.cfm?id=382250.382808.
(Unfortunately, you need an ACM subscription to see the full article.)

His plea didn't seem to convince many people to change.

Yuri Gurevich wrote a counterargument:
http://research.microsoft.com/~gurevich/Opera/69.pdf.

**Posted:** Thu Oct 25, 2007 5:48 am

_________________
Check out the Math Prize for Girls!

Kent Merryfield

Come to think of it, writing $=$ instead of $\in$ in a big-O situation is almost exactly the same thing as writing $=$ instead of $\equiv$ in a modular arithmetic situation. (And also the equals sign in Ravi's antiderivative.)

My earlier post may have been a little over the top, a little bit exaggerated. I do know how to be careful. One answer to the Fermatists is this: your notation must be widely enough accepted that it is comprehensible to your readers, and free of unnecessary ambiguities. (I didn't say free of all ambiguities - there are some that can be tolerated). Earlier I said that you have to be right. (And that's the primary defense of Euler - the man spent a lifetime being right far more often than he was wrong.) But the second commandment is that mathematics must be communicated.

To some extent, the earlier post arises from frustration with students who get so tied in knots worrying about verifying all the details of some formal definition that they never actually apply the tool to anything interesting.

**Posted:** Thu Oct 25, 2007 7:02 am

Ravi B

In the indefinite integral, if we define $C$ to be the set of constant functions, then I guess the integral equation is fine as is, with the equals sign.

**Posted:** Thu Oct 25, 2007 8:12 am

_________________
Check out the Math Prize for Girls!

fedja

Yes, I never said that my colleage was the first to propose the change.

As to the Gurevich's counterargument, extention of arithmetic operations to sets of objects is nothing new or unusual. Actually, when you think of it, the objects that are added are equivalence classes modulo some relation (and $1+o(1)$ as $x\to 0$ can be viewed as an equivalence class of functions containing $1$ where $f$ is equivalent to $g$ if $\lim_0 f-g=0$ ) more often than not. Even when we write $\frac 12+\frac 34$ , we are actually thinking of equivalence classes (otherwise, how do we change $\frac 12$ to $\frac 24$ ?), so why not classes of functions? As to his concluding remark that "=" simply stands for "is a", I can also say "Let's use $=$ for $\in$ , $\subset$ and God knows what else". Why not, indeed? The only really relevant remark he makes boils down to that "we understand our current notation sufficiently well, so there is no need to change it". Ancient Romans would probably say the same about their numerals and modern Americans say this about their measurement units every time the proposal to switch to the metric system arises Very Happy

.

On the other hand, Kent and Ravi B are certainly right that first, the notation should be a servant of a mathematician rather than his master and, second, there is absolutely no way to eliminate all inconsistencies in the mathematical language. Anyway, my goal was not to promote the point of view that is not even mine (I personally don't care and am completely happy with both $=$ and $\in/\subset$ language) but rather to say that the viewpoints may vary a bit here Smile

**Posted:** Thu Oct 25, 2007 9:00 am

Ravi B

**Posted:** Thu Oct 25, 2007 9:51 am

_________________
Check out the Math Prize for Girls!

mlok

I use an equivalent notation ( $\ll$ ) when explaining sequences and series, like
$\ln n\ll n^{0.1} \ll n \ll n^{10} \ll 2^n \ll 10^n \ll n!$
But I don't claim huge success in teaching this material, with or without the notation.

Once I came across an article (don't remember where) which advocated the approach to $O(\cdots)$ via $A(\cdots)$ , understood as any quantity whose absolute value does not exceed $\cdots$ . Like $\pi = A(4)$ , or maybe $\pi = 3 + A(1)$ , or better yet, $\pi = 3.1 + A(0.1)$ . This extends to functions pointwise: $\sqrt {x^2 + 100} = x + A(50x^{ - 1})$ for any $x > 0$ . If we don't particularly care if the constant is $50$ or $150$ , we can write $O(x^{ - 1})$ .

**Posted:** Thu Oct 25, 2007 10:42 am

Kent Merryfield

**Posted:** Thu Oct 25, 2007 11:50 am

fedja

The answer to Kent's question on whether we should introduce $o()$ and $O()$ in the classroom is "certainly yes". They became a standard part of the modern mathematical language and nobody doubts their convenience. On the other hand, the $o()$ - $O()$ thinking doesn't seem to be easy to grasp with any notation. Kent did a wonderful job explaining it in his handout but still not every student I showed this handout to "saw the light" at once, to say the least. The problem seems to root in "algebraic thinking" they get from high school where you need to solve everything exactly. A typical exercise I give is to find a $\delta$ for given $\epsilon$ for some limit and many students have difficulty with that not because they don't understand what is asked but because the idea that you can make a chain of rough estimates instead of solving inequalities exactly is completely new to them. $O()$ is pretty much the same story. I would probably start with something familiar like "an elefant pushes the cart forward, a horse pulls it to the right, a human pulls it back, and a mouse pulls it to the left. Where will the cart go?" and then, when seeing $n^2-2^n+3$ just ask "which one is the elephant here as $n\to\infty$ (or to $-\infty$ ) and which is the mouse". If they are able to answer that, one may start some formal language with them; if not, an attempt to formalize things will only confuse everyone...

**Posted:** Thu Oct 25, 2007 1:12 pm

Ravi B

**Posted:** Thu Oct 25, 2007 2:33 pm

_________________
Check out the Math Prize for Girls!

§outh§tar · Yang-Mills Theory Offline Joined: 09 Dec 2006 Posts: 722

If everyone understood what you said, did you really misspeak? Ninja

**Posted:** Mon Dec 31, 2007 11:10 pm

mathwizarddude

iff is short for "if and only if".

**Posted:** Sat May 24, 2008 2:17 pm

GaloisEva · New Member Offline Joined: 18 Jul 2007 Posts: 5

**Posted:** Fri Jul 11, 2008 11:36 pm

Mathstud28

I have always used the notation

$f(x)\ll{g(x)}$

to denote that $f(x)$ is "much less" than $g(x)$

Where what I think you guys are using it for is what I define with

$f(x)\prec{g(x)}$

Which means that $\lim_{x\to\infty}\frac{f(x)}{g(x)}=0$

Or in a more holistic sense, as x gets arbitrarily large that $g(x)$ "overpowers" $f(x)$ .

**Posted:** Tue Jul 15, 2008 4:51 pm

transseries · Poincare Conjecture Offline Joined: 02 Jul 2009 Posts: 170

What about this on page 2 ... $O(g_1(x))+O(g_2(x)) = O(\max(g_1(x),g_2(x)))$ ???
You have allowed $g_1(x)$ and/or $g_2(x)$ to be negative, after all.

**Posted:** Tue Aug 04, 2009 6:55 am