Talk:Big O notation

From Wikipedia, the free encyclopedia

Contents 1 ...Are you serious? 2 Correctness of section "Related asymptotic notations" 3 Algorithms and their Big O performance 4 Amortized complexities 5 Special name for O(n log n) 6 Etymology 7 Page moves, "Big O" vs other names 8 "is an element of" vs "equals" 9 Possible Correction 10 Little o 11 O vs. Θ 12 Name for n^n function 13 Other superexpoential names 14 Italicisation 15 Big O and little o 16 Big O and little o again 17 Move 18 Equation error? 19 Õ vs. Θ 20 Notation 21 Merge 22 Sublinear 23 Pronunciation 24 adding a constant 25 Table 26 Rename to asymptotic notation? 27 Notation mess - let's clean it up 28 Removed polylogarithmic 29 Changing Units

[edit] ...Are you serious?

"Big O notation"? It sounds like the name was created with the intention of teaching it to eight-year-olds... I can't believe that this is the accepted terminology. Unless I'm mistaken, "big O" stands for order (or some foreign equivalent), and in my experience in maths it's always been referred to as such. When I heard order notation formally introduced as "Big O notation" for the first time in computer science, I burst out laughing... You people are all mad :p. --203.206.183.160 14:38, 14 September 2006 (UTC)

You say that like madness is a bad thing :-). However, mad or not, we professionals call it "big oh" more than anything else, especially when we are talking to each other. McKay 06:16, 15 September 2006 (UTC)

Meet "Wikiality" my friend. Big-O is the most commonly used term for it, no matter how ridiculous it sounds. It's taught in college's around the country and most professionals use that term for it. Thus, if the populous says it's right, it's right. --20:18, 18 September 2006 (UTC)

[edit] Correctness of section "Related asymptotic notations"

Are the lim-sup and lim-inf definitions correct? I haven't seen them before. Reference this in the article, perhaps. Connelly 00:15, 9 August 2005 (UTC)

The lim-sup and lim-inf based definitions have vanished (in the table with the definitions). I do not know why (no comment was given at the appropriate changes), but the present lim based definitions of O,Ω,Θ are clearly wrong. Example: Consider the function f(n): = 1 for even n and f(n): = 2 for odd n. Clearly, it should be . But does not exist. Further, the definition of ω does not consider the absolute value of f / g. Then e.g. but (in contrast to the other definitions where a negation of f does not matter).

In the older revision link everything is correct. So unless there was a reason for the change I do not see, I think the table should be reverted to the old state. --DniQ 11:06, 11 March 2006 (UTC)

(the below moved from "Incorrect use of limits in table?" which is discussing the same thing):

Is the use of limits in the table of "relate asymtotic notations" correct? Knuth's definitions in the cited paper don't use them, and invoke instead "exist C and x_0 such that |f(x)| < C g(x) forall x > x_0". The "formal definition" section of this article (and linked articles) agrees with Knuth, but the limit in the table (it seems to me) doesn't say the same thing. Beyond that, Knuth's definitions are easier to read:

He wrote these on a typewriter but it's a good chance to excercise my Latex skills.

I propose changing the table to match Knuth's definitions, or else justifying the use of limits with at least a reference. 203.4.250.143 15:16, 5 September 2006 (UTC)

I didn't think about your proposal, but I'll agree that the current defs have problems. Consider f(n) = 1/n for odd n and f(n) = 0 for even n, and g(n) = 1 for odd n and g(n) = 0 for even n. Then f(n) = o(g(n)) by the usual definition but f(n)/g(n) fails to exist half the time so its limsup is undefined. McKay 04:04, 6 September 2006 (UTC)

So, when does it become appropriate to actually correct the article? (same user as quoted Knuth)

[edit] Algorithms and their Big O performance

I'd like to put in some mention of computer algorithms and their Big O performance: selection sort being N^2, merge sort N log N, travelling salesman, and so on, and implications for computing (faster computers don't compensate for big-O differences, etc). Think this should be part of this write-up, or separate but linked?

I think separate would be better, to increase the article count :-). Then you can have links from the Complexity, Computation and Computer Science pages. Maybe you can call it "Algorithm run times" or something like that. --AxelBoldt

Or something like analysis of algorithms or Algorithmic Efficiency since you may sometimes choose based on other factors as well. --loh

I'd recommend puting it under computational complexity which earlier I made into a redirect to complexity theory. It should be a page of it's own, but I didn't want to write it ;-) --BlckKnght

[edit] Amortized complexities

How about a note on amortized complexities? For instance, inserts and lookups in hashtables are O(1) amortized, in constrast with array lookup which is always O(1).

[edit] Special name for O(n log n)

doesn't O(n log n) have some special name ? --Taw

"linearithmic" was the term coined in Sedgewick, and adopted in some places. --Robert Merkel

I've also heard it called "log-linear" --Stormix

I've heard (and taught) "quasilinear" (because f=O(x^a) for all a>1, as close to 1 as desired), and think this is quite standard and also reasonable. (I plan to add this term on the main page if there is no protest against.) — MFH: Talk 13:02, 24 May 2005 (UTC)

I added loglinear, as that's how I've seen it in several books, and at least one other user has seen that (Stormix). Chris Connett 21:02, 21 December 2005 (UTC)

Well, you can also write it in soft-O, as in Õ(n). Is that "special"? --Rovenhot 00:46, 23 June 2006 (UTC)

But Õ(n) doesn't specifically mean O(n log n). Logarithmic factors are ignored, but it's not implied that there was one in the first place. --203.206.183.160 14:16, 14 September 2006 (UTC)

[edit] Etymology

The letter "O" comes from the word "order".

I remembering it as coming from the Latin word ordo. It makes a bit more sense as Landau, and Bachmann, bringing this notation to us, both were Germans. Obviously, it means the same, but I can see the difference. :) --Chexum

The german word for order/ordo would be Ordnung, so that's another possibility...but as Chexum said, the point is moot and these words are probably cognates anyway -- Magnus N.

[edit] 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)

"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)

[edit] "is an element of" vs "equals"

(Forgive the lack of mathematical notation...) Technically speaking, isn't it "f(x) is an element of O(g(x))"? In the article, "equals" is used. I think big O is the set of functions with the appropriate property. P3d0 13:06, 1 Aug 2003 (UTC)

Technically that is correct. The thing is that the "=" notation is long established; I would say most authors I have seen use "=" when writing about asymtotic bounds. I know that when I initially studied this, I would change the "=" to "" in my head, since by context the latter is correct. However, I, apparently like others, became accustomed to "=" notation that is (I think) more widely used.

In light of this, I notice that the article mixes these two freely. I think we should pick one or the other, and I nominate "=". If no one objects I'll change it, but add an explanation similar to the one above to the appropriate article (since this applies to all asymtotic notation, not just big-O) Chris Connett 20:59, 21 December 2005 (UTC)

[edit] Possible Correction

I noticed the statement that if

f(n,m) = n^2 + m^2 + O(n+m)

that this is like saying there exists N,C s.t. for all n,m >= N

f(n,m) <= n^2 + m^2 + C(n+m)

I would have thought that the O(n+m) is to be bounded in absolute value, i.e.

|f(n,m) - n^2 - m^2| <= C|n+m|

which leads to n^2 + m^2 - C|n+m| <= f(n,m) <= n^2 + m^2 + C|n+m|

Is this correct?

Steffan.

[edit] Little o

What does

where o is little o, mean?

Essentially it means that the "missing terms" go to zero "much faster" than x³ does, not just "at the same rate". Thus, for example, it could be that e^x = 1 + x + x² + x⁴ (not true, of course, but it would satisfy your "little-o" statement above). This works because as x goes to 0, the fraction x⁴/x³ doesn't just remain finite (big-O), it actually goes to 0 (little-o). - dcljr 05:14, 9 Jul 2004 (UTC)

[edit] O vs. Θ

The question is, should Wikipedia itself use Θ instead of O when both are correct, and the former is intended? (e.g. in discussing topics like the FFT and sorting.)

I have a computer-science background, and I know the difference between these two...however, I also know that Θ(...) is essentially unknown outside of computer-science circles, while O(...) is widely used and, informally, more-or-less understood to mean Θ. At a certain point, when usage becomes widespread enough, it ceases to be "incorrect" (it's only notation, after all).

One argument is that, since Θ is so little-known, its appearance will only confuse most people...thus, one should use O as long as it is correct (even if it is weaker than necessary) except in cases where one wishes to explicitly distinguish between the two. On the other hand, one could use Θ whereever possible, making the symbol a link to this page...requiring an extra page of reading for people not familiar with it, but hoping that most people will simply guess that the symbol looks like O so it means what they expect.

—Steven G. Johnson 07:00, 28 Nov 2003 (UTC)

I think that using Θ linked here should address most concerns. It does have the advantage of looking like O -- before I learned the precise difference I glossed it as 'something like O', and I imagine I wasn't alone. When the distinction matters it's bestto be precise. CRGreathouse (t | c) 04:12, 20 September 2006 (UTC)

[edit] Name for n^n function

I just added O(nⁿ) to the Common orders of functions table, mainly because I know it's often discussed in calculus classes. But I've never been able to find a name for this function (i.e., nⁿ or x^x). Does anyone have a name and source? - dcljr 04:53, 9 Jul 2004 (UTC)

Your edit seems to have been reverted, I don't know why (a comment could have been placed here). I think this could indeed be mentioned, but maybe we should wait for a name. I think for all that grows faster than exponential, one eventually takes the log and discusses the growth class of the latter. i.e.:

• c^n = exp( (log c)·n ) = exp( linear )
• n! ~ (n/e)^n = exp( n·(log n-1) ) = "exp( quasilinear )" (sorry I can't get used to linearithmic or so)
• n^n = exp ( n·log n ) = "exp( quasilinear )" , i.e. still the same ("exp-reduced") class.

— MFH: Talk 21:52, 21 Jun 2005 (UTC)

It sounds like a special case of a polynomial. I've never encountered a name for this, but you could call it an n^th degree polynomial. --Colonel panic 04:21, 24 September 2005 (UTC)

I do not think so. Polynomials have a fixed degree. What's more confusing: nⁿ grows faster than exponential, whereas polynomials grow slower than exponential. --NeoUrfahraner

If I recall correctly, it can be proven that O(nⁿ) = O(n!), using Stirling's approximation. So you could just call it "factorial order." Pmdboi 02:52, 25 May 2006 (UTC)

You recall incorrectly, sorry. McKay 01:30, 11 August 2006 (UTC)

n! < n^n < e^n n! for n at least 2. (This can be made more precice but messier: .) Thus n! is O(n^n). But I believe that n! < n^{n + ε} for ε < ½ and all n > f(ε), so n^n is not O(n!). CRGreathouse (t | c) 04:34, 20 September 2006 (UTC)

[edit] Other superexpoential names

I thought I saw a name for O) -- that is, exp(polynomial). Has anyone seen a name for this, or a name for O for that matter? CRGreathouse (t | c) 04:34, 20 September 2006 (UTC)

[edit] 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)

[edit] Big O and little o

What do the formal properties mean? In particular, what is the meaning of O(fg) = O(f)O(g)? --NeoUrfahraner 14:11, 18 Mar 2005 (UTC)

The only possible meaning of this would be that if h=O(fg), f'=O(f), g'=O(g), then h = O(f' g'), but the previous notation is indeed not completely well defined/correct. (The other way round, i.e. O(f) O(g) = O(fg) would be correct, however.) — MFH: Talk 13:46, 24 May 2005 (UTC)

Thank you --NeoUrfahraner 06:25, 27 May 2005 (UTC)

[edit] Big O and little o again

What I am missing on this page is remarks on the relation between the various notions, in particular between Big-O and little-o. Intuitively, it seems that f=o(g) iff f=O(g) and g!=O(f). The "only if" direction of this claim is clearly true, but I am not so sure about the "if" direction. Is it true? If yes, it should be noted in the section discussing Big o and little o. If it is not true, there should be a brief remark why this is the case.

After a bit more thinking, I see now that the converse of the above does not hold. Take the following functions:

f(n) = 2^n if n is even, and n if n is odd

g(n) = 0.5 n

Then f=O(g), g!=O(f), an f!=o(g). I guess the converse holds only for monotonic functions.

In fact g=O(f) in that example. You need f(n)=n, g(n)=mixture of n or 2^n. McKay 14:48, 29 June 2006 (UTC)

You're correct as far as I can tell. One way of fixing this might be to say that f=o(g) iff f=O(g) and f≠Θ(g). Deco 11:41, 29 June 2006 (UTC)

No, put f(n)=g(n) for even n and f=g(n)/n for odd n. I don't think there is a simple rule like this. McKay 14:48, 29 June 2006 (UTC)

[edit] Move

This should really be moved to order of growth, asymptotic growth of a function, or something to that effect. Describing orders of growth in an article called "Big O notation" makes about as much sense as describing limits in an article called "limit notation", addition in an article called "summation notation", or for that matter mathematics under "mathematical notation". Of course, the notation must be described, but that's not the primary purpose of the article. Fredrik | talk 11:40, 10 November 2005 (UTC)

There is already an article at Asymptotic notation that duplicates much of this information as well, and a shorter one at asymptotic analysis that treats the basic concept without reference to the O-notation. I agree that there should be some consolidation and rationalization of titles and content. Perhaps this should all be merged into asymptotic analysis, which will discuss the concepts, and mention the notation where appropriate? E.g. there is a concept "asymptotic dominance", and little-omega is a common way this is written. --Delirium 02:37, 18 November 2005 (UTC)

[edit] Equation error?

In the "Multiple Variables" section, shouldn't the second equation,

   \forall n, m>N:f(n,m) \le n^2 + m^3 + C(n+m). 

end in just "+ C.", since C is just some constant and doesn't depend on n and m?

The ambiguous notation suggests a function called C, but intends C times n+m. I'll fix it. Deco 02:28, 16 December 2005 (UTC)

[edit] Õ vs. Θ

You find Õ instead of Θ (theta) at many places in the article. is this correct? --Abdull 12:50, 3 March 2006 (UTC)

No, that's wrong. Õ is soft-O, which means that logarithmic factors are ignored. Big-Theta, Θ, means that the function is guaranteed to have that particular order--no more, no less. --Rovenhot 00:52, 23 June 2006 (UTC)

[edit] Notation

Two comments on notation.

1. As someone stated above, "=" is much more common than "is" or so it should be used throughout with the other notations given only as alternatives.
2. The explanation given for "f(x) = h(x) + O(g(x))" is inadequate. Strictly speaking it is correct, but it does not allow for slightly more complex statements like "f(x) + O(j(x)) = h(x) + O(g(x))" or even "f(x) = h(x) + O(g(x))+ O(j(x))". Such patterns are commonplace in asymptotic analysis. Also consider "n^O(1)=O(eⁿ)". I'll try to formulate a general rule.

McKay 11:36, 15 June 2006 (UTC)

Agreed. Frankly I'm not entirely certain how those are intended to be formally intepreted, but I think the rearrangement trick should work. Deco 12:43, 15 June 2006 (UTC)

I'm a mathematician, and I can honestly say I have never seen the "element of" notation used in connection with the big O notation. Is this something that's common in computer science? If not, it should be deleted from the article.--209.43.9.143 19:19, 19 June 2006 (UTC)

No, it isn't common in computer science either. There are some popular textbooks that use it but it has not caught on amongst the professionals. Despite the oddities of how "=" is used with O( ), it is what the vast majority of mathematicians and computer scientists use, so we should use it too. McKay 03:18, 20 June 2006 (UTC)

Everyone in practice seems to use the "=", but I think it's important to at least mention the element of syntax. While few texts stick to it, the majority of those that introduce Big O (in my memory, at least) usually give a sentence or two about it (usually with a word or two of how the world might be a better place if it was used instead).

[edit] Merge

I see a merge suggestion on the top of the page but I don't think there is a case for it? Should it be removed then? -- ^Evanx(tag?) 05:54, 22 June 2006 (UTC)

Seems to me that the two pages are on almost exactly the same topic, so the case for merging seems pretty good. McKay 00:11, 29 June 2006 (UTC)

I disagree. I think a page with big O and little O notation on it would be too long and it's worth having seperate pages for them. Meekohi 05:38, 6 July 2006 (UTC)

However Landau notation includes both big and little O so that's not a good argument. McKay 08:53, 6 July 2006 (UTC)

What's the point of having big O and little o in two separate articles? Seems artificial to me. 141.20.53.108 18:05, 7 September 2006 (UTC)

Definitely merge. —Steven G. Johnson 13:37, 6 July 2006 (UTC)

Definitely merge under the title "Landau notation" and make this page a redirect. 141.20.53.108 18:00, 7 September 2006 (UTC)

I think that this article should stay where it is. Merging content from Landu notation can be done as needed. CRGreathouse (t | c) 13:01, 20 September 2006 (UTC)

[edit] Sublinear

Should not the small o be used in the example of where sublinear is written? helohe (talk) 14:23, 28 July 2006 (UTC)

It isn't clear. Sometimes "sublinear" is used to mean O(n), with the "sub" deriving from the fact this is an upper bound. I wouldn't accept the terminology in a paper without a definition because of this ambiguity. McKay 04:43, 29 July 2006 (UTC)

[edit] Pronunciation

So how do you pronounce "O(n)"? [1] says it's pronounced big oh of n. Maybe we should add that? -- Felix Wiemann 18:35, 9 August 2006 (UTC)

Every computer scientist I've ever heard would say O(n) as "linear complexity with respect to n". Every mathematician I've ever heard would say "(of the) order of n". --203.206.183.160 14:07, 14 September 2006 (UTC)

I've heard "O of n" and "the order of n" and occasionally the theoretically-ambiguous "linear". CRGreathouse (t |

c) 04:37, 20 September 2006 (UTC)

I've heard most commonly "Big Oh of n", "Oh of n", and "Order of n". Of course, I've never heard anybody says that something "equals" O(n), which seems to be the preferred notation on here.

[edit] adding a constant

This claim is wrong:

unless g(n) = o(1), in which case it is O(1).

A counterexample is to take g(n)=1/n if n is odd, and g(n)=n if n is even. A correct sufficient condition would be g(n)=Ω(1) but Ω has not been introduced in the article yet. McKay 00:58, 11 August 2006 (UTC)

[edit] Table

Are there any objections, corrections, or suggestions to this modification of the table?

Notation	Name	Example
O(1)	constant	Determining if a number is even or odd
O(log* n)	iterated logarithmic	The find algorithm of Hopcroft and Ullman on a disjont set
O(log n)	logarithmic	Finding an item in a sorted list
O((log n)c)	polylogarithmic	Deciding if a number is prime with the AKS primality test
O(n)	linear	Finding an item in an unsorted list
O(n log n)	linearithmic, loglinear, or quasilinear	Sorting a list with heapsort
O(n2)	quadratic	Sorting a list with insertion sort
O(nc), c > 1	polynomial, sometimes called algebraic	Finding the shortest path on a weighted digraph with the Floyd-Warshall algorithm
O(cn)	exponential, sometimes called geometric	Finding the (exact) solution to the traveling salesperson problem
O(n!)	factorial, sometimes called combinatorial	Determining if two logical statements are equivalent [2]
	double exponential	Finding a complete set of AC-unifiers [3]

Changes:

• I removed supralinear from n log n. I've never seen it with this particular meaning outside of Wikipedia, but I have seen it used to mean "superlinear". In any case it's uncommon.
• I removed an incorrect entry with nⁿ as "exponential".
• I added double exponential to the table.
• I added examples of all complexities.
• I removed the sublinear row. This should be mentioned somewhere, but it doesn't really fit on the table (all others could be expressed with Θ, for example).

Things that might need work:

• I'm not happy with my example for factorial complexity; is there a more standard example? Ideally it would be ω(cⁿ) for all c.
• AKS is usually thought of as polynomial (in the size of the number rather than in the number itself); should I use a different example then for polylogarithmic complexity?
• Should I specify both constants in the double exponential, or should I leave one fixed for simplicity's sake?
• Is there a term for the 'epsilon complexities'? I'm thinking in particular of O(n^n+ε) = O(n^o(1)) (the first is for all ε > 0), but others also come up. This is a wider class than just soft-O of n; it would include, for example, n (log(n))ⁿ.
• Is there a term for sublinear complexities of the form O(n^c), like baby-step giant-step?
• I'm not terribly happy with the wording of the examples in general; if you have a better idea, please suggest it.

General notes:

• The purpose of the examples is to give an idea of the kinds of problems these classes represent. I'm less worried about specifying them precisely than I am of keeping them simple; the entries on the individual classes can iron out any wrinkles. As such, I don't intend to mention, for example, that oddness and evenness can be tested for in constant time only when the number is represented in an even base not dependant on the number.

CRGreathouse (t | c) 07:31, 20 September 2006 (UTC)

[edit] Rename to asymptotic notation?

I merged asymptotic notation and Landau notation into this page, following the longstanding merge tags, as those pages were (almost) complete subsets of the information on this page, and this page had received by far the most attention of the three (and thus should have its history preserved).

However, now that they are merged, there is an argument for moving this page and its history to asymptotic notation, as that title seems broader.

On the other hand, since this page had received the most attention of the different titles, it seems that editors have already voted with their feet. Also, in common usage, the term "Big O notation" seems to be a synecdoche for asymptotic notation in general.

What do people think?

—Steven G. Johnson 15:40, 26 September 2006 (UTC)

I like it as it is now -- Big O notation as the main page, with other pages like Hardy notation and Vinogradov notation explaining variants on it. Because Big O is biggest by far, it gets all the basics of asymptotic notation, but doesn't have to define other less common terms (which can be done at their own pages). CRGreathouse (t | c) 06:36, 27 September 2006 (UTC)

[edit] Notation mess - let's clean it up

The article at the moment uses a real mess of different notations. This won't do. We should choose a single notation and use it throughout except for a section that describes alternative notations. The only suitable default notation is the one using "=" because that is what is used 99.9% of the time in professional mathematics and CS. Anyone disagree? McKay 08:17, 16 November 2006 (UTC)

Much as I dislike that abuse of notation, I must agree. It is the only standard (although I wouldn't say 99.9%, probably more like 99.5%). CRGreathouse (t | c) 08:57, 16 November 2006 (UTC)

[edit] Removed polylogarithmic

Reinstated my VERY bad. Missed a bracket

[edit] Changing Units

In the properties section there is a paragraph on the effects of changing units. This implies that doing so can affect the order of the algorithm, which sounds counter-intuitive.

It also says (in part): "If, however, an algorithm runs in the order of 2ⁿ, replacing n with cn gives 2^cn = (2^c)ⁿ. This is not equivalent to 2ⁿ (unless, of course, c=1)." I thought the actual base of the exponent was irrelevant, and we simply used base 2 as a convenience for computer nerds who are used to thinking in binary. (2^c)ⁿ is still a constant base, and so it's still O(2ⁿ)

Any comments? Am I right? Gazimon 11:07, 5 December 2006 (UTC)

No, the article is correct. e.g. 2ⁿ is o(3ⁿ), i.e. asymptotically smaller. Just look at the ratio (2ⁿ) / (3ⁿ) = (2 / 3)ⁿ, which goes to zero for large n.

Possibly you are confusing this with logarithms. In a logarithm, changing from log_a(n) to log_b(n) is just a constant factor log_a / log_b that is irrelevant to big-O notation.

—Steven G. Johnson 18:01, 5 December 2006 (UTC)