Talk:Big O notation/Archive 2

Archive 1

Archive 2

Archive 3

Archive 4

Not all O(n) created equal

Would it be worth mentioning somewhere in the article that two algorithms can have the same complexity, yet one may be significantly faster for real-world implementations? For example, if algorithm A takes n seconds and algorithm B takes 10^9*n seconds, obviously A is a billion times faster even though both algorithms are O(n) (even $\Theta (n)$). Though this may be obvious to those of us familiar with the notation or with limits in general, this may be entirely unobvious to novices. Thoughts? I'm not sure if this would be encyclopedic enough to warrant inclusion. Mickeyg13 (talk) 21:22, 18 September 2008 (UTC)

That should be in some other article about computational complexity, not here in an article about mathematical notation. —David Eppstein (talk) 14:39, 19 September 2008 (UTC)

Some of this ground is covered in Cobham's thesis, but it would be nice to have a general discussion somewhere of how the big-O runtimes of two algorithms only describes their relative performance in the limit (for sufficiently large inputs). Perhaps analysis of algorithms. Dcoetzee 00:13, 16 January 2009 (UTC)

recent change - truncated series

"In mathematics, it is usually used to describe how closely a truncated infinite series (especially an asymptotic series) approximates the value of the original untrucated series, by characterizing the residual terms of the series."

This is not right. There might not be any untruncated series, or, as in the case highlighted (asymptotic expansions), the untruncated series might diverge. A O() term is used to indicate how accurately the truncated series approximates the original function, not how accurately it approximates the infinite series. Here is my attempt:

In mathematics, it is commonly used to describe how closely a finite series approximates a given function, especially in the case of a truncated Taylor series or asymptotic expansion.

McKay (talk) 13:39, 19 September 2008 (UTC)

Thanks for the improvement to my wording. —David Eppstein (talk) 14:40, 19 September 2008 (UTC)

Article is too complex

I just read the article, as I've heard the term O(n) several times by hackers when referring to things like filesystem performance.

However, I don't understand it one bit. The article looks like it's been written for those that already understand it, which is crap. Can somebody write it in a format that's actually understandable by human beings?

I'm not stupid. I've written a ton of simple algorithms, do PHP+MySQL programming as a hobby, and have written C and Delphi in the past. I did an IQ test recently, and it came out as 121. Yet I cannot understand this article. Something is fundamentally wrong. --121.44.28.236 (talk) 23:03, 11 March 2009 (UTC)

You can say, "Hey, this article is poorly written," without getting into how smart you are/aren't. I think most people would agree with you on the nature of the article, but going off about how smart and accomplished you are just comes across as obnoxious. Especially when an IQ of 121 alongside remedial programming experience hardly warrants bragging rights.74.137.25.150 (talk) 23:09, 21 April 2009 (UTC)

It really doesn't matter what IQ you have, bragging rights regarding IQ dont exist. The subjective nature really downplays any sense of taking you seriously. I'm not stupid. I cant program, i don't know how to make something simple in html. I never felt like learning. I suggest you use that high IQ and use it to learn this format, its not very difficult. delta, epsilon, < , > , iff , things like this are not intuition to understand, but this is the basics. Its just nice looking at a proof and realizing why its trivial, opposed to an equation given, a few numbers being plugged in and then just taking it as that this applies always. no need to dumb it down for yourself. —Preceding unsigned comment added by Shk9664 (talk • contribs) 13:29, 7 December 2009 (UTC)

I lolled at this because I don't consider ~120 to be very special and taking it as offensive that someone should use it to claim some credibility towards intelligence seems a little off. (I'm quite aware of the incomplete view of a person's intelligence an IQ gives, the ability to train it, etc. It just always seems to kind of hold true that higher IQ's are smarter people, with exceptions to the rule.) On the subject of this article complexity, yeah that happens a lot on Wikipedia. Lots of people with different backgrounds (educationally as well) trying to create a single defining and objective view of a subject, it tends to become a mess of formal and correct definitions without much education value (and sometimes little referential value).

Article is too verbose

I think there is too much "stuff" in this article that is only marginally useful. IMHO it would be more helpful if it were pared down a little. I would be happy to try to make changes along these lines by axing some stuff, but I'm not sure of the etiquette for undoing other people's work. (It is also slightly inconsistent in its use of O(.) and Theta(): e.g., in the "Orders of common functions" table, the implication is clearly that the example algorithms have at least the running time shown.) Alex Selby (talk) 23:31, 17 April 2009 (UTC)

There are lots of small problems and the structure is like a dog's dinner :). A complete careful rewrite would be a nice assignment for someone other than me! McKay (talk) 12:37, 18 April 2009 (UTC)

Superexponential

(Just watching recent edits.) I didn't know about the "super-exponential" in the tetration sense, but in practice (or at least in computer science and analysis, where Big O notation is used) AFAIK "superexponential" does usually mean 'something that grows faster than exponential'. Shreevatsa (talk) 14:52, 16 July 2009 (UTC)

Either way, the anon's change is wrong. "Something that grows faster than exponential" means $2^{\omega (n)}$ or $2^{n^{\omega (1)}}$ depending on your definition of "grows exponential", not $O(n^{n})$. — Emil J. 15:10, 16 July 2009 (UTC)

Right, "superexponential" doesn't mean $O(n^{n})$, but I've seen books consider $n^{n}$ superexponential since it's $2^{n\lg n}$ which is $2^{\omega (n)}$ (and so is $n!$ for that matter). Anyway, after seeing the table I agree that the anon's change is wrong, as the "name" of $O(n^{n})$ is not "superexponential". Shreevatsa (talk) 15:28, 16 July 2009 (UTC)

Yes, that's what I meant. The function $n^{n}$ is itself superexponential (in the sense used here), but there are functions in $O(n^{n})$ which are not superexponential (e.g., $2^{n}$), there are superexponential functions which are not $O(n^{n})$ (e.g., $2^{2^{n}}$), and replacing $O(n^{n})$ with $\Omega (n^{n})$ does not help either (there are functions like $2^{n\log \log n}$ which are superexponential, but not $\Omega (n^{n})$). — Emil J. 15:57, 16 July 2009 (UTC)

It's also not clear what point it serves in being there. It's a simple formula, but it's difficult to come up with examples where it comes up. The closest I can think of is Cayley's formula for spanning trees, but that's off from this by a quadratic factor. —David Eppstein (talk) 16:09, 16 July 2009 (UTC)

I simply removed the entry, as it was not "commonly encountered when analyzing algorithms". Problem solved. :) — Miym (talk) 16:23, 16 July 2009 (UTC)

Complex uses

That section heading made me think of complex numbers. Perhaps we could reword this. Professor M. Fiendish, Esq. 07:25, 25 August 2009 (UTC)

Correctness of the "Orders of common functions" table

I believe that $\left(n^{c}\right),0<c<1=O\left((\log n)^{c}\right),c>1$ (not the other way around). So the table is wrong. Am I wrong? — Preceding unsigned comment added by 189.122.210.182 (talk) 22:59, 24 September 2009 (UTC)

Yes, you're wrong. $(\log n)^{c}=O(n^{d})$ for any $c,d>0$ --Robin (talk) 23:14, 24 September 2009 (UTC)

Product property

Shouldn't we add that the product property is valid only when $x\to \infty$? Here it says that given $f_{1}\in O(g_{1})$ and $f_{2}\in O(g_{2})$ then $f_{1}f_{2}\in O(g_{1}g_{2})$. This if false if $x\to 0$ (and maybe also if x goes to any scalar k?): let's say that we have $f_{1}=a+bx^{2}$ and $f_{2}=x^{2}$ ($a$ and $b$ constants). Now, clearly $f_{1}\in O(x^{2})$ and $f_{2}\in O(x^{2})$. However, $f_{1}f_{2}=ax^{2}+bx^{4}$, and by the definition given $f_{1}f_{2}\in O(x^{2})$ as $x\to 0$; more importantly, $f_{1}f_{2}\notin O(x^{4})$, which invalidates the property. In the case I'm getting it all wrong, please do correct me, that would be very helpful! :) --Roberto^→@me 17:20, 18 November 2009 (UTC)

$f_{1}\notin O(x^{2})$ as $x\to 0$, unless a = 0. — Emil J. 17:25, 18 November 2009 (UTC)

Ooook, then it would be $f_{1}\in O(1)$, with $a\neq 0$. That makes sense, thanks. --Roberto^→@me 17:32, 18 November 2009 (UTC)

Subexponential vs Quasipolynomial

Quasipolynomial time is a notion which is rapidly becoming common usage among algorithm designers, especially those working in approximation algorithms. However, such a definition is missing here. I am adding it to the table, and I added it to the blurb on subexponential time. -- deeparnab —Preceding unsigned comment added by Deeparnab (talk • contribs) 17:25, 1 December 2009 (UTC)

There's something of a terminology issue, since quasipolynomial is sometimes used to mean, "polynomial in the input" (rather than in the number of bits of the input), i.e., exponential. But as long as we're careful to define it wherever it's used, I see no problem. I agree that it's an interesting class. CRGreathouse (t | c) 02:33, 2 December 2009 (UTC)

I've never heard quasi-polynomial being used in the sense of "polynomial in the numeric value of the input". Pseudo-polynomial time seems to be the commonly used term for that. --Robin (talk) 03:57, 2 December 2009 (UTC)

Maybe I'm just confusing the two? CRGreathouse (t | c) 20:49, 3 December 2009 (UTC)

Limit conditions for big-Omega and big-Theta?

We have that $f=O(g(x))$ iff

$\limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty .$

Should we also add similar conditions for big-Omega and big-Theta bounds? I was surprised to not find them in the article.

If I recall correctly the appropriate conditions are $f=\Omega (g(x))$ iff

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty$

and $f=\Theta (g(x))$ iff

$\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=c$ for some $0<c<\infty$

These conditions can be useful in practice for finding asymptotic bounds on some less friendly functions. 24.224.217.167 (talk) 02:44, 18 February 2010 (UTC)

You recall incorrectly. It is possible for $f=\Omega (g(x))$ and yet for $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}$ to not be defined, and similarly for Θ. For instance, let f be the 3x+1 function that maps x to x/2 when x is even and to 3x+1 when x to odd, then f(x)=Θ(x) but no limit of f(x)/x exists. It's possible to get a correct version using lim inf, lim sup, and absolute values, but even the lim sup version that you quote from the article is incorrect without the rest of the context from the article: g must be nonzero for all sufficiently large x. —David Eppstein (talk) 03:55, 18 February 2010 (UTC)

Unclear sentence

In the section on little-o, the clause

while the former has to be true for at least one constant M the later need to be true for any positive constant.

doesn't make clear just what "the former" and "the latter" refer to, especially since the definition of Big-Oh does not appear there for comparison.

Also, "latter" is misspelled, and some of the language in this section just ain't English:

...if and only if, for any positive constant M, exist a constant x₀, such that...

should be

...if and only if, for every positive constant M, there exists a constant x₀, such that...

and

...the latter need to be true ...

should be

...the latter need be true ...

I also changed "for any" to "for every" in the first correction above, following Jim Baumgartner's advice many years ago at Dartmouth: since "any" can be ambiguous, it's safest to avoid using it at all, especially since we don't really need it; "some" and "every" suffice. So I also prefer

... the latter need be true for every positive constant.

As a general comment, I've always encouraged students to pronounce f = O(g) as "f is of order no more than g" so as to discourage the kind of misuse of Big-Oh that Knuth objects to in [6].

Finn (John T) (talk) 14:14, 28 May 2010 (UTC)

• 1. As to the linguistic questions, I mostly agree with you, and I'll try to improve the language in the little o section. Actually you could have done that yourself; it is in fact perfectly permissible for the wikipedia readers to edit the articles... (Since you did not do the changes yourself, I'll follow my own mind, however. E.g., I usually treat "need" as a modal auxiliary verb only in negated sentences; i.e., "He needs to do it" but "He need not do it".)
• 2. As for the way to read a text fragment like f = O(g) : Different ways to pronounce it should be and partly are introduced early in the article. I've been a bit surprised not to find the "order" pronounciation, which was the first English one I met (in one of the classical "Cambridge University texts", as far as I remember). Mainly, I met the Swedish tradition, using the (Latin?) word "ordo". However, I'm not going to touch the parts about actual usage in English. I do note, that at least one mathematical text book author consistently avoided the equal sign, in order to lessen the chances of student errors; instead of "f = O(g)", he wrote "f is O(g)". Contributions about English usage at the top of the article would be welcome, especially if you provide sources for the recommendations you make and follow. JoergenB (talk) 17:42, 17 June 2010 (UTC)

Little o notation

In the little o notation section, $o(f)\subset O(f)$ is mentioned as a fact. As it's the only place in that section where $\subset$ appears, I can only assume that someone went out of his way to say that it's a proper subset, that is, for any $f$ there is a function bounded but not dominated by $f$. Now, this is clearly true for all $f$ except the constant zero function (or something locally identical to it for all sufficiently large $x$), which means that it's pretty much true whenever you would use it, but I can't see anything that strictly disallows $f$ to be constantly zero. Have I missed something? 85.226.206.92 (talk) 05:42, 29 July 2010 (UTC)

This page needs an overview for the non-mathematicians amongst us

I've been studying algorithms at a fairly simple level and was looking for some helpful information on Big-O - but I scanned this page and very quickly gave up - and I wonder how many others do too. A simple table showing the various common O's in order (similar to this one I eventually found: http://leepoint.net/notes-java/algorithms/big-oh/bigoh.html) and perhaps a graph showing them visually would be a huge help to everyone looking for introductory information on the topic - otherwise it just puts people with little mathematical background off the topic. —Preceding unsigned comment added by Essentialtech (talk • contribs) 22:14, 1 November 2010 (UTC)

Subscripts

This page needs to address the meaning of subscripts on the O somewhere, as in

$f(x)=O_{\varepsilon }(x^{1+\varepsilon })$

meaning that the constant implicit in the big O notation is allowed to depend on ε. RobHar (talk) 22:24, 13 April 2011 (UTC)

Is this standard? Can you give a source? McKay (talk) 05:42, 22 June 2011 (UTC)

It is quite standard, but no I don't have sources see, for example, Terry Tao and Van Vu's book Additive combinatorics, page xvi. RobHar (talk) 12:50, 14 September 2011 (UTC)

"which means that O(g) is a convex cone"

This links to an article which defines a convex cone as a certain kind of subset of a vector space. If the statement is true, it would be interesting to see more discussion of the vector space of big O sets: how exactly it's defined. Or does the writer only mean "somewhat analogous to a convex cone". Dependent Variable (talk) 16:23, 17 April 2011 (UTC)

About "Formal definition"

The last user to revert my edit says in the edit summary "that's not the standard usage of the term; that definition would not allow log(x) = O(x^e) for e > 0, for example."

x→∞ always means both directions, that is, x→+∞ and x→-∞. This is the standard, at least in calculus and mathematical analysis. If there is another convention in computer programming, you should point it out and reference it. I think you most likely confused the real number x with natural number n, the latter being the one used most often in programming and since n is always non-negative, n→∞ equals n→+∞. For instance, log(x) = O(x^α) is indeed not correct, but log(n) = O(n^α) is.--Netheril96 (talk) 03:12, 21 May 2011 (UTC)

Huh? I'm a math grad student and if I saw x→∞ I'd think that meant just x→+∞. Your claim seems strange to me. JoshuaZ (talk) 02:54, 25 May 2011 (UTC)

Fair enough. I just read the Wiki entry on limit. Apparently Chinese convention is different from American one (I'm a Chinese student).--Netheril96 (talk) 03:16, 25 May 2011 (UTC)

x → ∞ in complex analysis can mean that x is going off to infinity in any direction, and in that field O() might cover any such path to infinity. Often you see statements like "f(x) = O(g(x)) if x → ∞ with arg(x) in some interval". In real analysis, usually x → ∞ means x → +∞ and x → -∞ is different. So Netheril96 has a point, though I'm not sure of the best way to handle it in the article. McKay (talk) 03:47, 25 May 2011 (UTC)

That's a good point about the complex case. Maybe just note explicitly that the exact definition changes slightly depending on the ring in question? JoshuaZ (talk) 04:10, 25 May 2011 (UTC)

calligraphic O

This issue was raised by me before but no action was taken. Now I propose to take action:

Proposal: The notation ${\mathcal {O}}(f(n))$ (calligraphic O) should be replaced by $O(f(n))$ (italic O).

Reason: $O$ is vastly more common in the literature than ${\mathcal {O}}$. I am a specialist in asymptotics but the only times I ever see the calligraphic version are on this page and when I look at Concrete Mathematics. But Concrete Mathematics is an old book and its notation did not become mainstream. Author Don Knuth uses $O$ in his more recent works, including the authoritative Art of Computer Programming, Vol. 4. Standard modern references like the CRC handbook and NSIT handbook use $O$. As far as I can tell, none of the 30 or so books on analysis of algorithms, or similar number of books on asymptotic analysis, that I have on my shelf use ${\mathcal {O}}$. One or two use a roman $\mathrm {O}$, but all the rest use $O$.

So, I'm going to change it unless someone makes a pretty good case for keeping ${\mathcal {O}}$. McKay (talk) 02:56, 31 May 2011 (UTC)

Sounds good to me. It would be a good idea to consistently use O on other pages, e.g. Sorting algorithm. (Many other algorithm pages already use O or O, such as Divide and conquer algorithm, Fast Fourier transform, and Heap (data structure).) — Steven G. Johnson (talk) 17:52, 31 May 2011 (UTC)

I think we should be using the italic O rather than the Roman — the slant makes it easier to distinguish from the digit 0. And I suspect it's the variation most frequently used in research publications, in no small part because that's the default behavior of TeX when one puts an O in an equation. —David Eppstein (talk) 18:12, 31 May 2011 (UTC)

Hm, maybe it's only in the Swedish literature that ${\mathcal {O}}$ is commonly occurring; if it's not common in the English literature, then of course it shouldn't be used in this article and so it wasn't that good to change to it, my bad. --Kri (talk) 22:42, 2 June 2011 (UTC)

Just a note: Concrete Mathematics does not use ${\mathcal {O}}$. It just uses math fonts in which all symbols (and even digits) look somewhat handwritten, including the ordinary O (from Euler Text, not Euler Script Capitals). Marc van Leeuwen (talk) 11:24, 14 September 2011 (UTC)

On the $\ll$ notation.

The article is a bit obscure about the origin of the $\ll$ notation. It mentions Hardy as the one proposing it, but there is no reference given. The Hardy-Littlewood paper Some Problems of Diophantine Approximation that is mentioned in the relevant section does not use this notation as far as I can see. The Order of Infinity paper of Hardy also does not mention this notation; it uses $x\prec y$ to say that $x/y\to 0$, which is what the article says the meaning of $x\ll y$ is. Did I miss something in one of those papers? Dorian in the skies (talk) 08:03, 10 June 2011 (UTC)

It's usually called Vinogradov notation, so I suspect it came from one of the Vinogradovs. CRGreathouse (t | c) 15:58, 10 June 2011 (UTC)

OK, thanks. But then, the article needs to mention this. In addition, I believe the Vinogradov notation implies that $x\ll y$ is equivalent to $x=O(y)$, and this is not what the article says. Dorian in the skies (talk) 21:10, 10 June 2011 (UTC)

It isn't clear to me that the article should spend time on obsolete or rare notations, as it is already way too long. Perhaps a spin-off article could contain these things along with the history of such notations. McKay (talk) 05:44, 22 June 2011 (UTC)

absolute values in Omega and Theta notations

The article at the moment defines Ω() and Θ() using absolute values. No source is given. It makes perfect sense to use the absolute value for O(), as most sources do, but it is less clear for Ω() and Θ(). Knuth's famous SIGACT article uses absolute value for O() only. Can someone please check Vol 1 of TAOCP (3rd edn), section 1.2.11.1? To be precise, I'm wondering why we define $f(n)=\Omega (g(n))$ as

$|f(n)|>=cg(n){\mbox{ for }}n\geq n_{0}$

rather than

$f(n)>=cg(n){\mbox{ for }}n\geq n_{0}.$

People in asymptotic combinatorics like me usually use the second version, for example we write $n^{-\Omega (1)}$ for a function decaying faster than some negative power. People in algorithms only ever use it for lower bounds on positive things so it makes no difference to them. McKay (talk) 06:11, 22 June 2011 (UTC)

I agree with you on this point, but I don't have my copy of TAoCP handy. CRGreathouse (t | c) 19:19, 22 June 2011 (UTC)

Well, I did it. McKay (talk) 04:55, 29 June 2011 (UTC)

Article is too technical

I simply want to be able to compare the efficiency of computer programs and, in particular, sorting algorithms. This is something that is useful for people who want to understand information technology. This article presupposes a knowledge of mathematics and mathematical notation that the reader might not have. For example, the articles on sorting algorithms use the 'Ω' symbol, so I went to this article to look up the meaning of 'Ω' but this article explains it using a formal definition. (It is especially annoying when textbook authors and Wikipedia editors alike refer to difficult mathematical concepts as "trivial.") I understand the need for precision in formal definitions, but can you please also provide informal definitions that are actually comprehensible? (As I see it, the point of a general encyclopædia is to impart knowledge to the public, rather than merely to share it amongst experts.) 69.251.180.224 (talk) 17:44, 30 June 2011 (UTC)

The article defines defines Ω in a table whose columns include one entitled "intuition". There it says "f is bounded below by g (up to constant factor) asymptotically". Is it the word "asymptotically" you have a problem with (or maybe "bounded below")? It's a complicated enough concept that it's not something you can really express in every day terms. Humans didn't naturally evolve language to express that one thing was always smaller than something else but yet could be thought of as being the same size (which is what can happen here). RobHar (talk) 12:44, 14 September 2011 (UTC)

Order-Theoretic Information

People who learn about the O-notation often expect is to induce a total quasi-order, at least on ascending functions on the positive numbers, which means that if f and g are two such functions, at least one of $f\in O(g)$ or $g\in O(f)$. This is not true in general, but there are papers that prove it for functions composed using some basic operations (like sums, products, exponents) and even discuss order-theoretic properties of this set. However, I cannot recall the bibliographic references. I for one would be thankful if somebody could help in including such information in the article.

AmirOnWiki (talk) 10:13, 12 July 2011 (UTC)

"Differentiability in quite general spaces"

The article currently states (in the Generalizations and related usages section):

The "limiting process" x→xo can also be generalized by introducing an arbitrary filter base, i.e. to directed nets f and g. The o notation can be used to define derivatives and differentiability in quite general spaces [...]

Could someone who knows more about this topic rewrite this to be more precise and specify what those "quite general spaces" are, perchance? I'd be quite interested. Thanks! 82.82.131.70 (talk) 23:01, 22 September 2011 (UTC)

Anyone? Or, alternatively, does anyone have any suggestions for further reading in the form of books or articles? Thanks! 82.83.138.118 (talk) 15:49, 27 October 2011 (UTC)

Maybe try Bourbaki. Just a guess. Marc van Leeuwen (talk) 17:18, 27 October 2011 (UTC)

That section of our article is next to useless without some references, or at least wikilinks that lead to an explanation. McKay (talk) 02:08, 28 October 2011 (UTC)

Forgive me if I'm totally wrong...

but for programming, wouldn't it be easier to just give f(x,y,z,...) where the parameters to the function are the parameters to the algorithm? e.g.

function badSum(number x, number y, number z) { number sum; for(number i = x; x > 0; x--) { sum = sum + 1 } sum = sum + y + z; return sum; }

would have

f(x,y,z) = x+2

or the like?

Forgive me if I'm stupid. — Preceding unsigned comment added by 75.72.68.21 (talk) 01:26, 20 April 2012 (UTC)

Page moves, "Big O" vs other names

Please do not move pages

• to less common names (see Wikipedia:Naming conventions (common names))
• without fixing double redirects

--Eloquence 15:12 29 May 2003 (UTC)

1. I believe big oh notation is more common in formal writing. Please refer any CS textbooks. You should find big oh not big O.
2. because some people may be against the new name like you, so I have to take some time to waint and see.

-- Taku 15:16 29 May 2003 (UTC)

Google shows that "Big O" is twice as common, if you claim that "Big Oh" is more common in textbooks, collect a sample of at least ten random textbooks and demonstrate that more than 5 of them use "Big Oh". --Eloquence 15:24 29 May 2003 (UTC)

Sure. -- Taku 15:26 29 May 2003 (UTC)

I also vote against the move to "Big oh" until / unless cites are presented to show that it is now the common use: maybe my CS training is old-fashioned, but I recall the use of "big O" thoughout. However, show me the evidence, and I'll be willing to change my mind. The Anome 15:27 29 May 2003 (UTC)

Of course, people use big O because it's quick to write than big oh. My claim is isn't big oh notation is common as formal notation. Anyway give me some time. I think I can prove that. -- Taku 15:37 29 May 2003 (UTC)

Here is the result of my research. I couldn't find out ten books containing either big O notation or big oh notation but what is common usage seems apparent.

1. Paul Walton Purdon, Jr. Cynthia A Brown. "The analysis of algorithm" uses Big O notation as the title of a chapter.
2. Horowitzw, "Fundamentals of computer algorithms" - in a section Asymptoic Notation ".... One these is the O-notation"
3. Herbert S.Wilf "Algorithms and Complexity" "...are following five "o" (read 'is little oh of'), 'O' (read is 'big oh of'), ...."
4. Donald E. Knuth "The art of computer programming" "The O-notation. .... This is the "big oh" notation, ...."
5. B.M.E Moret H.D.Shapiro "Algorithms from P to NP" "2. Mathematical techniques: 2.1. Big Oh, Big Omega, Big Theta Notations"
6. Robert Sedgewick "Algorithms" 2nd ed. "... The mathematical artifact for making this notion precise is called the O-notation, or "big oh notation," ...."
7. Steven C. Altheoen, Robert J.Bumcrot "Introduction to Discrete Mathematics" "... f(n) is said to be of order of maganitude g(n), written f(n) = O(g(n)) and read "f(n) is big oh g(n),"
8. * Johnsonbaugh Richard, Discrete mathematics 5th ed. Macmillan, New Jersey - "An expression of the form f(n) = O(g(n)) is sometimes referred to as a big oh notation for f."

Except two books, all books I grabed at random above use big oh notation. -- Taku 19:11 29 May 2003 (UTC)

I think some of them may be saying how to pronounce big-O. Still, Knuth is usually pretty canonical. Can we call the article "O-notation", and direct both big-O and big-oh here? The Anome 19:23 29 May 2003 (UTC)

Isn't that the same case in omega and theta? My impression is that he O-notation or the big-O notation is in the same line with big-Θ and big-Ω because O is typically in italic like big-O notation while you cannot italize characters on the Internet.

Besides, actually I want to suggest to name this article asymptoic notations because we certaily want to cover little oh, big-theta and big-omega as well as big-oh.

-- Taku 19:33 29 May 2003 (UTC)

Actually no,

1. Big O
2. O
3. O pronounced as "big oh"
4. O pronounced as "big oh"
5. Big Oh
6. O-notation pronounced as "big oh notation"
7. Big Oh
8. Big Oh

Only three out of 8 refer exclusively to "Big Oh". The other clarify O-notation to be pronounced "Big Oh", this is to avoid confusion with a zero. We already avoid this by having the text "with a capital letter O, not a zero". I see no reason to change the title from "Big O notation", since this is what Google likes the most, perfectly correct and does not require us to fix any double redirects (the way I know Taku's moves, he probably won't do it himself). However, a redirect here is of course acceptable.

The page should only be moved to asymptotic notation (note singular) if it actually covers other types of this notation, not in the expectation that it will at some point. --Eloquence 19:37 29 May 2003 (UTC)

I don't think so. From the excerpts Taku posted it seemed to be that the 2nd and 3rd books were saying the *symbols* o and O stand for little-oh and big-Oh, hence those books used big-Oh as the principle name, not on how to pronounce them. Really, i have not seen any CS book including pronunciation directives. The 6th book furthermore indicates both names are used, but seems to prefer the O-notation. Score: 6 vs 8. In my opinion, if anyone cares, it should be big-Oh. The whole pronunciation thing does not make sense at all since the English pronunciation of O and Oh is quite similar. Furthermore, Wikipedia is the first source in which I see big-Oh spelled as big-O. 131.211.23.78 12:48, 14 September 2007 (UTC)

"the way I know Taku's moves, he probably won't do it himself". What do you mean by this? If you were suggesting I am lazy, it is not the case. I leave old redirects deliberatly so that it's easy to revert my new move. I think it is preferable that move the page and wait for a while to see what other think, while some disagree with this though.

-- Taku 19:46 29 May 2003 (UTC)

No, in case of a much-linked page, it's preferable to

1. Propose the move on the talk page with arguments. Announce that you will move the page within a few days if there are no objections.
2. If a consensus is reached, move the page and at the very least, fix double redirects (in this case, without editing the redir at Big O, 45 links would suddenly become broken).

It is not desirable to leave Wikipedia in an inconsistent state (in this case, 45 links that suddenly show the user a confusing redirect page, because of the double redir caused by your move) because your move would then be "easier to revert". It should not have to be reverted, because it was properly discussed first.

You have the annoying habit of simply moving pages around without prior discussion, in the expectation that people will complain if they disagree. That's correct, they will complain, bud they will also get pissed. If you want to avoid that, discuss first, move later. --Eloquence 19:52 29 May 2003 (UTC)

Show me actual examples that annoyed you. If I remember, most of the times, I discuss first and correct redirects if needed. I usually post a proposal at talkpage first. What case are you taking about? Besides, you think this time I should discuss first, but actually you can regard moving as a kind of suggestion. You can think I suggested a new name. If you disagree, you can just revert it. This is the same process to achive NPOV in articles. It is part of discussion. You don't have to be pissed off at all. -- Taku 02:27 30 May 2003 (UTC)

Sorry I think the comment above is not good. Hostility is the last thing we want. I can see oftentimes I piss you off. For example, the last time of datadump. We should be able to have fun not have fight. So my apology of moving this article suddely and I have made a decision that I won't move any article altogether because I don't want to risk to annoy/piss off people. You may think it is extreme but I think it is safe to me because I am often careless. You can see the statement about this in my userpage. -- Taku 03:10 30 May 2003 (UTC)

For what it's worth, the Dasgupta, Papadimitriou, and Vazirani Algorithms uses "Big O" rather than "Big Oh". CRGreathouse (t | c) 23:06, 21 September 2006 (UTC)

---

Anyway above is completely off-topic. Eloquence, you claim Goolgle likes the number of hits with"Big-O notation" is twice as much as that of "Big-oh notation". It is true (by the way, "big o-notation" with 6,450 while "big oh-notation" with 2,990). But my impression is that although big o outweights big-oh, pages with good and formal writing seem to use big-oh notation. First it is consistent with other notations, big-omega and big-theta. Omega and theta are pronounciation of each letter, but so is big-O. Besides, see the list above. Only one textbook uses Big-O notation. I think it is logical to think that the sentence like

O, &Omega and &Theta (big-Oh, big-Omega, big-Theta) are used in CS. And this is called big-oh notation. I don't mean to be scarstic but I think I am trying to discuss, though maybe I am wrong. -- Taku 15:17 31 May 2003 (UTC)

---

Big-Oh notation is used in "Big Java, 2nd Edition" by Cay Horstman on page 712. Superslacker87 11:49, 15 July 2006 (UTC)

Two important points:
1. Search engine "tests" are not Wikipedic : refer to WP:SET
2. This notation hasn't originated in computer science, so the constant reference to computer science needs sme justification. I wonder whether WP attracts an unrepresentatively large number of computer scientists, rather than (say) pure mathematicians, thus skewing the discussion.
—DIV (138.194.12.224 (talk) 06:42, 30 August 2012 (UTC))

Italicisation

I know this is a really minor point, but can we standardize the italicization of O? Is it O(n) or O(n)? It's displayed both ways on this page. — Caesura 19:17, 20 Nov 2004 (UTC)

In the TeX markup for the TeXbook, Knuth uses $O(n)$. That's just a big O in "math mode", but it would be rendered in italics, like a function name in TeX's math mode. The equivalent wiki <math> markup would be <math>O(n)</math>, which is rendered as $O(n)$, or it could be approximated by ''O(n)'', which is rendered as O(n). —AlanBarrett 16:46, 15 Dec 2004 (UTC)

Remains the difference in math mode: $O\left(n\right)$ versus ${\mathcal {O}}(n)$. I'm not sure which is more conventional. I think many scientific articles just use the capital O instead of \mathcal{O}, probably because it's shorter. —145.120.10.71 12:12, 14 April 2007 (UTC)

As far as I can see, the logical formatting would be roman, not italic, if the symbol is treated as a function. See references

• Mills, I. M.; Metanomski, W. V. (December 1999), On the use of italic and roman fonts for symbols in scientific text, IUPAC Interdivisional Committee on Nomenclature and Symbols
• Typefaces for Symbols in Scientific Manuscripts, NIST, January 1998.

cited at Italic_type#When_to_use, with URL's.
—DIV (138.194.12.224 (talk) 06:38, 30 August 2012 (UTC))

Fractional powers of n ordering in table

If I'm not mistaken O(n^c), 0 < c < 1 can be moved to the top of the table of function growth ordering as it always grows slower than O(1). Is that right/wrong? — Preceding unsigned comment added by 124.169.2.38 (talk) 01:51, 4 August 2012 (UTC)

You are wrong. O(1) doesn't grow at all. McKay (talk) 03:39, 1 September 2012 (UTC)

Formal Definition

Under "Formal Definition", the statement:

limsup as x->a | f(x)/ g(x) | < infinity

only holds for functions whose values are in the same field, since the two values must be compatible if you want to divide one by the other.

To have the statement hold for functions with arbitrary normable values (like, for example, two different metric vector spaces), the absolute value bars should go around each of the functions f and g, instead of their quotient:

limsup as x->a | f(x) | / | g(x) | < infinity — Preceding unsigned comment added by Soulpa7ch (talk • contribs) 18:47, 19 November 2012 (UTC)

Archiving this page

This page is large, so any objections to setting it for autoarchive at 90 days? Glrx (talk) 17:31, 20 November 2012 (UTC)

Wouldn't it be better to call this article "Big-O notation" for consistency?

I notice that the section on "Little-o notation" has a hyphen. I personally prefer the hyphen and think it makes more sense. Also, if you look at "Big O" disambiguation page, there are a lot of things referred to as "Big O" and no others which are "Big-O". I would suggest renaming this "Big-O notation," and having "Big O notation" redirect to the renamed page. Natkuhn (talk) 03:51, 25 December 2012 (UTC)

That's a good point. I agree that "Big-O notation" makes grammatically more sense, and it is in accordance with WP:HYPHEN.—Emil J. 13:48, 25 December 2012 (UTC)

Article Complexity

As someone wanting to discover big O notation, I find this article far too complex far to early in the text. I really do believe that the only people able to understand this article are those who are already expert in its use and thus don't need it. Thus the article is redundant. It would be much better if it started of a bit gentler. Right now I beleive it does more harm than good as it scares people off of wanting to learn big O notation. Scottie UK. 01:00, 04 March 2013 (GMT) — Preceding unsigned comment added by Scottie UK (talk • contribs)

"Big O" What ?

Just started loling after stumbling upon this. But it seems to be real. big-O, little-o, f little-o g, serious? Why would you say that? Whats wrong with "f grows slower than g"? Too much complexity to summarize? Calling it omnikron couldn't be to hard either. Please rename article to Landau notation. 91.51.114.77 (talk) 06:10, 15 January 2013 (UTC) 91.51.114.77 (talk) 06:10, 15 January 2013 (UTC)

While the historical notation for asymptotic notation is pretty horrible, saying "f grows slower than g" is entirely imprecise.

Having the name Landau notation as an alias probably isn't so bad, but most people know the topic by the name "Big Oh notation" and not by any other. Tac-Tics (talk) 22:46, 11 March 2013 (UTC)

Editorializing about Knuth

Before May 28, this article strongly favoured the computer scientists' version of big-Omega over the number theorists', which was bad. But the discussion now has heavy editorializing against Knuth's introduction of the computer scientists' version. Others have remarked on this (in edit comments and tags) but nobody has changed it, perhaps since it's so well referenced. So I am taking that editorializing out, while leaving in the facts (most of which were already elsewhere in the page). —Toby Bartels (talk) 16:45, 22 June 2013 (UTC)

Infinitely Many

Seems like "infinitely many" in the table for the big omega description is not very descriptive. Shouldn't it be "for all n" rather than for infinitely many n? Richard Giuly (talk) 21:32, 14 August 2013 (UTC)

No, it's correct as it is. For instance sin(x) is Omega of 1, because |sin(x)| is larger than 1/2 (say) for infinitely many x (but not for every x).Sapphorain (talk) 23:46, 14 August 2013 (UTC)

Big Omega is defined in many ways, including "for all sufficiently large n", but the "infinitely many n" is common and is useful in cases like Sapphorain's example. Also consider a problem which is trivial for odd input size and needs n³ time for even n: it is useful to be able to say it is Ω(n³). McKay (talk) 05:22, 15 August 2013 (UTC)

Other arithemtic operators

In Big_O_notation#Other_arithmetic_operators, it says that $O(n^{2})+55n^{3}+2n+10$ can be replaced with $n^{2}$. Shouldn't this be $n^{3}$ since $O(f(x))+O(g(x))=max(O(f(x)),O(g(x))$? Made the edit accordingly

50.136.177.227 (talk) 16:17, 25 September 2013 (UTC)

No, you are misreading it. It is saying that the "O(n^2)" within the formula can be replaced by something else. It is not talking about simplifying the whole formula. —David Eppstein (talk) 16:56, 25 September 2013 (UTC)

Abuse of notation in definition of big O

There is no algorithm that "equals" big O of anything. Big O is a function from a set of functions to another set of functions. So when one writes O(expression), this denotes a set of functions. It is inconsistent to write that any algorithm equals O(expression), because an algorithm is not a set. Furthermore, even if that issue were fixed, it is imprecise and misleading to say that an algorithm is in a big O set. The algorithm itself cannot be compared with the elements of a big O set, which are mathematical functions. It is more precise to indicate that a mathematical function that expresses a property of the algorithm is in some big O set.

For example, it would be incorrect to say that mergesort is in O(n log n), but it would be correct to say that the work of mergesort as a function of input size n is in O(n log n). — Preceding unsigned comment added by 128.237.218.106 (talk) 11:33, 16 October 2013 (UTC)

No. There is no abuse of notation. The relation "=" used here is NOT the standard equality, and I agree that this is misleading. According to Hardy and Wright (Theory of numbers, Oxford 1938), the expression "f=O(g) means that |f|<Ag,[...], for all values of [the variable] in question“ (so in this first definition "f=O(g)" is considered as one single symbol, and "=" has no meaning of its own). They write: "O(g) denotes an unspecified f such that f=O(g)"; thus the symbol "O(g)" does not denote a set, but an unspecified element of a certain set. They give the example "O(1)+O(1)=O(1)=o(x)", and finally note: "It is to be observed that the relation "=" asserted between O or o symbols , is not usually symmetrical". And if one finds this too confusing, there is the alternate Vinogradov notation <<, which entirely avoids all these problems... Sapphorain (talk) 15:14, 16 October 2013 (UTC)

Mnemonics

(Below "Family of Bachmann-Landau notation" table)

This "mnemonics" business appears very unclear and clumsy to me. I strongly suspect it is the private production of a well-intentioned wikipedia contributor. Neither Bachmann, nor Landau, nor Knuth (at least in the references cited) mentioned anything close to what is claimed below the "Bachmann-Landau" notation table. Knuth uses the word "mnemonic" in his paper, but only to refer to the fact that the symbol O is commonly used and has become a reference. I note in passing that the "mnemonic" concerning the Omega symbol refers to the Knuth version of this symbol, and not to the Hardy-Littlewood version (which is the only one Landau knew): so who in the world is supposed to have devised these mnemonic "recipes"? I still think a precise reference is very much needed to justify the conservation of this part in the article. Sapphorain (talk) 21:21, 3 September 2013 (UTC)

It looks much like OR to me. It would definitely need a proper source attribution, but anyway, I’m unconvinced this bit of trivia needs to be included in the (already quite long) article at all.—Emil J. 12:17, 4 September 2013 (UTC)

I suppressed the bit of trivia. The bibliographic references inside were suppressed too, but can be found elsewhere in the page. Sapphorain (talk) 22:08, 16 November 2013 (UTC)

f(x) versus f

Currently in this article, the notation f(x) is used to denote a function. In the articles Function (mathematics), Limit (mathematics) etc., f is used to denote a function (a rule for mapping numbers to numbers) and f(x) is unambiguously used to denote its value (a number). These are two different approaches to the notation of functions: in the first approach (used in this article), the letter f denotes a dependent variable or (physical) quantity, and when talking about the function's behavior, one must always say what variables are regarded as the independent variables or experiment parameters that it depends on; in the second approach (in Function (mathematics) etc.), f is the name of a function, where function is defined as a rule mapping objects to other objects. Perhaps the notation of functions should be unified in Wikipedia? 90.190.113.12 (talk) 12:34, 9 January 2014 (UTC)

Base of log?

Sorry if I missed it, but I couldn't find specified anywhere what base of log is being used. Does it not matter since it is only comparing orders? Or is it assumed to be base 2 since it's computer science? Thanks for any clarification. — Preceding unsigned comment added by 68.250.141.172 (talk) 20:06, 23 January 2014 (UTC)

The base of the log does not matter once it is moved inside of Big-O. Changing the log base involves multiplying by a constant. Glrx (talk) 22:21, 25 January 2014 (UTC)

Hardy and Littlewood's $\Omega$ Notation Section Is Problematic.

Not only is the paper incorrectly cited, but if you read the paper (available here: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC1091181/pdf/pnas01947-0022.pdf), the letter Omega does not appear.

Discussion of the definition of limit superior as x approaches infinity is also absent from the paper, which is a relief because $\limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|$ appears non-sensical to me. How can x approach infinity from above?

I'm inclined to strike this section from the page.

Thoughts?

76.105.173.109 (talk) 20:49, 17 February 2014 (UTC)

You are looking at the wrong paper. The right one is here (probably behind a paywall, sorry). Also, there is nothing in that formula which says that x is approaching infinity from above. Incidentally, they do not use limsup in their definition and returning to the original version might help people with poor analysis background (like most computer scientists). Here is what they say:

We define the equation f = Ω(φ), where φ is a positive function of a variable, which may be integral or continuous but which tends to a limit, as meaning that there exists a constant H and a sequence of values of the variable, themselves tending to the limit in question, such that |f| > Hφ for each of these values. In other words, f = Ω(φ) is the negation of f = o(φ).

I think that the condition H > 0 is required and was omitted accidentally. McKay (talk) 04:13, 18 February 2014 (UTC)

Incidentally, this is the definition most used in computer science even though that is rarely admitted. Consider an algorithm that takes time n² for even n and is trivial (constant time) for odd n. This happens all the time but everyone writes Ω(n²) even though it does not satisfy the textbook definition of Ω that they claim to be using. McKay (talk) 04:13, 18 February 2014 (UTC)

Proper way to 'say' Big-O notation

I am not a native English speaker. I was wondering if this article should mention the proper, or any, way to say Big-O in spoken English. For instance, I don't know which one better: "this algorithm has a Big-O of n squared," "this algorithm has a complexity of n squared," or "this algorithm is n squared."

This discussion seems to be settled here Negrulio (talk) 20:24, 10 June 2014 (UTC)

This is also referred to as "Order Notation"

eg. f(x)=O(x^2) would be stated as "f(x) has order x squared". It may be a North American way of calling this, but no-one in Australia or Britain ever calls this "Big O Notation". It sounds very childish. We simply refer to this as "Order Notation" which is what the original author called it.

There appears to be some confusion here. "f(x) has order x squared" is usually abbreviated by $f(x)\asymp x^{2}$. "f(x)=O(x^2)" has a very different meaning, which could (somewhat unprecisely) be worded as "f(x) is at most of order x squared" (with the understanding that f(x) could very well have an extremely irregular behaviour, with no clear order to speak of. Sapphorain (talk) 08:52, 12 June 2014 (UTC)

Caption

In the box on the top right, the caption should have a equals sign. — Preceding unsigned comment added by 81.129.12.48 (talk) 13:07, 21 August 2014 (UTC)

It should be "f(x)=O(g(x)))". — Preceding unsigned comment added by 81.129.12.48 (talk) 13:10, 21 August 2014 (UTC)

MIT Lecture notes source cites Wikipedia

The source "Big O Notation (MIT Lecture)" references Wikipedia. It seems the citation refers to only a small part of the material in the lecture notes. This is, of course, a Bad Thing, but the source seems otherwise sound. Is it ok to keep?

Wootery (talk) 16:03, 1 September 2014 (UTC)

Reorganise the article

The article is hard to read, sorry. Too much information, many duplications. I suggest at least moving a part of the section 6.4 "multiple usage", the properties of non-symmetry of the notation to the properties of the notation, since this seems to be an important property under the given non-symmetric definition. Sources lacking. Fixed a mathematical mistake. --Yaroslav Nikitenko (talk) 15:39, 8 October 2014 (UTC)

Infinitesimal asymptotics -- bringing it down to introductory students

Reorganization of a WP article is tricky and I have not read this article carefully enough to make such a recommendation. Having said that, it seems to me that the article starts at a rather abstract level. Keep in mind that I am judging from the narrow perspective of teaching first year college engineering students. I like to link to WP articles in my teaching, and your organization is no problem because I can link down to the subsection I need. In this case it would be:

Big_O_notation#Infinitesimal_asymptotics

I usually make these links out of Wikiversity (e.g. Physics equations). In your article, I made the example more explicit by showing first and second order expansions for the same expression. I hope you don't mind. If you like the edit, and also make the request, I can try to align the two text sections embedded in the equations.

Yours truly,

--guyvan52 (talk) 15:03, 31 January 2015 (UTC)

Little-o notation: Graham.Knuth.Patashnik.1994 vs Sipser.1997

‎Sapphorain reverted my remarks on a deviating definition by Sipser, stating that Sipser.1997's definition is equivalent to that of Graham.Knuth.Patashnik.1994 (given before in the article). She/he is probably right, as I didn't think much about this issue.

However, the article says about Graham.Knuth.Patashnik.1994's definition:

If g(x) is nonzero, or at least becomes nonzero beyond a certain point, the relation f(x) = o(g(x)) is equivalent to $\lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.$

while Sipser.1997 says f(n) ∈ o(g(n)) if

$\lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0$

i.e. he doesn't require g(x) to becomes nonzero beyond a certain point.

Moreover, the article says about Graham.Knuth.Patashnik.1994's definition:

g itself is not [in little-o of g], unless it is identically zero near ∞

while Sipser.1997 says:

g(n)∉o(g(n)) for all g

i.e. he doesn't require g not to be identically zero near ∞.

For these reasons, I felt (and still feel) that both definitions slightly differ.

In particular, the ‎Sapphorain's statement (in the edit summary) "a function is never a o of itself (in either definition!)" appears to challenge the restriction "unless it is identically zero near ∞" made in the article; if s/he is right, that restriction is confusing and should be removed. - Jochen Burghardt (talk) 15:44, 7 March 2015 (UTC)

There is no reference for any paper or book by Sipser published in 1997 on MathSciNet. Anyway, if one uses the usual definition for a limit, once g(x) become identically zero beyond a certain point, the ratio f(x)/g(x) is not defined, for any f, and in particular g(x)/g(x) is not defined. So the limit does not exist, and in particular cannot be 0. Thus as you expose it here, what you write doesn't make sense. So I assume something must be missing in what you are trying to reproduce from Sipser's publication. Sapphorain (talk) 16:26, 7 March 2015 (UTC)

You are right: g can't be 0 infinitely often when the limit exists. I overlooked that Sipser (see "Further reading" in the article for the full reference) requires the range of f and g to be the set of positive (i.e. >0) reals. Sorry for the confusion. - Jochen Burghardt (talk) 18:52, 7 March 2015 (UTC)

What about O(x^x) ?

Is it its own class? Or where does it belong to? --RokerHRO (talk) 13:55, 19 March 2015 (UTC)

74.111.162.230 (talk) 16:04, 1 May 2015 (UTC) Using exponential identities it can be shown that x^x=E^(x ln(x)) so it is faster then an exponential but slower then E^(x^(1+ε)) for any ε>0. It is about as fast as the factorial as explained here.

It grows more quickly than factorial, but only by a lower-order (single exponential) factor. —David Eppstein (talk) 16:14, 1 May 2015 (UTC)

"Abuse of notation"

It is a fact that some consider the usual way of using the O notation an abuse of notation, but it is also a fact that some others don't. It is not the role of wikipedia to teach its readers what they should consider. Sapphorain (talk) 19:35, 7 July 2015 (UTC)

It is not just a matter of taste. For example, n ∈ O(n), and n+1 ∈ O(n) are both obvious from the definition. Writing "=" for "∈" invites to apply symmetry and transitivity of "=" to conclude n=n+1. While the latter may still be interpreted in a meaningful way (reading "=" as "has the same complexity class as"), it is tempting to read "=" as "has the same value as", and to infer 0=1 by subtraction of n on both sides. Maybe, the article should explicitly warn about this fallacy. - Jochen Burghardt (talk) 22:54, 7 July 2015 (UTC)

But it is a matter of taste. And there is no fallacy. In the original definition, which has been in use since Bachmann and Landau, and which is clearly stated at the very beginning of the article (in the first section "formal definition"), the expression "f(x)=O(g(x))" is defined as a whole: the symbols "=" and "O" are not separately defined, and the equality sign does not denote here an equivalence relation. What you call the definition is just another, and more recent, definition. Some like it better, some don't. So it is quite sufficient to state in the article that some consider "f(x)=O(g(x))" an abuse of notation. Because some others don't. Sapphorain (talk) 04:12, 8 July 2015 (UTC)

I agree with Sapphorain. The view that =O is a single comparison operator (not a misused equality sign with a function on the left and a set of functions on the right) is perfectly consistent and is the view taken by some sources. When there is disagreement over an issue like this, it should be our position here to describe both sides of the issue, not to take sides. —David Eppstein (talk) 05:45, 8 July 2015 (UTC)

Inappropriate reference deleted

I suppressed a reference in the lead to a so-called "MIT Lecture". I'm very skeptical regarding this denomination, but there is another reason for the deletion: The source given at the end of the "lecture" is … the big oh page of wikipedia! (and an old version, as it begins by stating that the symbol O was invented by Landau, which is false). Sapphorain (talk) 08:57, 10 July 2015 (UTC)

Hardy–Littlewood definition

The section "The Hardy–Littlewood definition" contains this sentence:

Hence $f(x)=\Omega _{R}(g(x))$ is the negation of $f(x)<o(g(x))$, and $f(x)=\Omega _{L}(g(x))$ the negation of $f(x)>o(g(x))$.

I'm a bit horrified to see inequality relations used with little-o at all, but if one must try to derive a meaning for it I see ≤ and ≥ rather than < and >. McKay (talk) 04:52, 31 August 2015 (UTC)

In the classical (number theory) notation, f(x)<o(g(x)) means that f(x)<h(x), for some h(x)=o(g(x)), and f(x)≤o(g(x)) means that f(x)≤h(x), for some h(x)=o(g(x)): so the two notations are exactly equivalent.

Regarding references for the notations $\Omega _{+},\Omega _{-},\Omega _{\pm }$, I put Ivić 1985 book, but this is not very satisfactory. I recall I used this notation much before 1985 (it was for instance systematically used by the number theory group at Urbana-Champaign in the late 70s), but I have been unable to find who actually used it first.Sapphorain (talk) 08:34, 31 August 2015 (UTC)

"big O" or "Big O"?

This article is not consistent wrt. "big O" vs "Big O" (case). What should it be? --Mortense (talk) 10:04, 5 February 2016 (UTC)

Yes, I didn't notice. In my opinion, "big" is just a regular adjective here, that should take a lower case b, except of course at the beginning of a sentence. The upper case B (mostly at the end of the article) should I think be all replaced by lower case b. Sapphorain (talk) 10:28, 5 February 2016 (UTC)

Agreed, "big O" is appropriate except beginning a sentence. - CRGreathouse (t | c) 17:55, 5 February 2016 (UTC)

… Done (I hope). Sapphorain (talk) 20:01, 6 February 2016 (UTC)

Suppressed imprecise references in the lead

I have suppressed the two references in the lead, which were (and this is an understatement) very imprecise. The first one, while correctly reporting the first use of O by Bachmann, and its adoption by Landau in 1909, asserted it was "included in a more elaborate notation which included o(.), etc". It is true that Landau adopted the symbol O and invented the symbol o in 1909. But that's it. So the last "etc" in the author's assertion indicates only one thing: that he himself never read Landau's book. The second one asserted that both symbols (o and O) were first introduced by Bachmann in 1894. Which is false. So I replaced these references by Bachmann's and Landau's books. Sapphorain (talk) 20:36, 3 July 2016 (UTC)