Talk:Big O notation
|
|
| Contents |
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
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).
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(xa) 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)
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
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)
- I believe big oh notation is more common in formal writing. Please refer any CS textbooks. You should find big oh not big O.
- 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.
- Paul Walton Purdon, Jr. Cynthia A Brown. "The analysis of algorithm" uses Big O notation as the title of a chapter.
- Horowitzw, "Fundamentals of computer algorithms" - in a section Asymptoic Notation ".... One these is the O-notation"
- Herbert S.Wilf "Algorithms and Complexity" "...are following five "o" (read 'is little oh of'), 'O' (read is 'big oh of'), ...."
- Donald E. Knuth "The art of computer programming" "The O-notation. .... This is the "big oh" notation, ...."
- B.M.E Moret H.D.Shapiro "Algorithms from P to NP" "2. Mathematical techniques: 2.1. Big Oh, Big Omega, Big Theta Notations"
- Robert Sedgewick "Algorithms" 2nd ed. "... The mathematical artifact for making this notion precise is called the O-notation, or "big oh notation," ...."
- 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),"
- * 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,
- Big O
- O
- O pronounced as "big oh"
- O pronounced as "big oh"
- Big Oh
- O-notation pronounced as "big oh notation"
- Big Oh
- 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
- 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.
- 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)
"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)
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.
Little o
What does
- <math>e^x=1+x+x^2+o(x^3)\ {\rm as}\ x\rightarrow 0<math>
where o is little o, mean?
- Essentially it means that the "missing terms" go to zero "much faster" than x3 does, not just "at the same rate". Thus, for example, it could be that <math>e^x=1+x+x^2+x^4<math> (not true, of course, but it would satisfy your "little-o" statement above). This works because as x goes to 0, the fraction x4/x3 doesn't just remain finite (big-O), it actually goes to 0 (little-o). - dcljr 05:14, 9 Jul 2004 (UTC)
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)
Name for n^n function
I just added O(nn) 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., nn or xx). 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)
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 (http://www.ctan.org/tex-archive/systems/knuth/tex/texbook.tex), 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 <math>O(n)<math>, or it could be approximated by''O(n)'', which is rendered as O(n). —AlanBarrett 16:46, 15 Dec 2004 (UTC)
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)