Talk:Big O notation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
          This article is of interest to the following WikiProjects:
WikiProject Computing (Rated B-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.
 
WikiProject Mathematics (Rated B-class, Mid-importance)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
B Class
Mid Importance
 Field: Analysis
One of the 500 most frequently viewed mathematics articles.
This article has comments.
WikiProject Computer science (Rated B-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
B-Class article B  This article has been rated as B-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
This article has an assessment summary page.

Algorithms and their Big O performance[edit]

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

Removed polylogarithmic[edit]

Reinstated my VERY bad. Missed a bracket

"Tight" bounds?[edit]

The article refers to terms "tight" and "tighter", but these terms are never defined! Alas, other pages (e.g. "bin packing") refer to this page as the one giving a formal definition of this term; moreover, "Asymptotically tight bound" redirects here. Yes, the term is intuitively clear, but a math-related page should have clear definitions.

I think a short section giving a formal definition of the term "tight bound" and referring to Theta-notation is needed (e.g. as a subsection of section "8. Related asymptotic notations"), and once such a section is created the redirection from "Asymptotically tight bound" should link directly there.

What about O(xx) ?[edit]

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

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, nO(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[edit]

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)