Talk:Big O notation

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 recomend 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

---

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

---

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

---

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

---

Please do not move pages

• to less common names (see Wikipedia:Naming conventions (common names))
• without fixing double redirects (see Wikipedia:How to use redirect pages).

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

---

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)