Talk:Big O notation

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Improper use of subscripted Omega symbols[edit]

The symbols (Omega_H) and (Omega_K) have only been used in one single article (Vitanyi-Meertens), in which the authors essentially disapprove of the various Knuth definitions of asymptotic symbols, and approve the Hardy-Littlewood definition of Omega: they thus propose to change the definitions of the other Knuth symbols accordingly. (It is of course needless to point it, but let's point it anyway: this proposition has never been adopted by anybody). Moreover the subscripts K and H are used there only in order to label the two different definitions of the various symbols, similarly as a formula label and set in parentheses on one side of the formula or assertion they label. These subscripts have otherwise never been used in the literature, and certainly not in place of the symbol Omega in one of its two usual meanings. It is thus not proper, even for clarity purposes, for a wikipedia article to replace the symbol Omega by subscripted versions which are never used elsewhere. Sapphorain (talk) 22:47, 14 March 2017 (UTC)

Aha, I see we were typing at the same time :). I agree about this. --JBL (talk) 22:57, 14 March 2017 (UTC)

Edits to table[edit]

Mathnerd314159 has recent made two edits to the big table in the section Family of Bachmann–Landau notations; I reverted the first, and the second was responsive to my edit summary. However, I still have some qualms about the edit. In particular:

  • I rather like the informal definitions, which take the (useless and incomprehensible) formal definitions and present them in a few words. (How strongly do I feel that they are better than the limit definitions that have been added instead? Not terribly.)
  • The citation-dump in the table title sections is silly and not very helpful for purposes of verification.
  • I do not find the explanation "from smallest to largest" helpful at all; am I correct that it is not supported by the citation? The analogy to orderings on the real line is ok, except for (trivial) it duplicates one symbol and (not trivial) the symbol ≈ has no fixed meaning.
  • Finally, and most importantly, I object to the invented notations and . No one uses such notations, and it is not good practice to invent new notations for Wikipedia articles.

I am happy to discuss ways to resolve these issues. (I'll go take care of the trivial one right now.) --JBL (talk) 22:52, 14 March 2017 (UTC)

(1) Can you explain more why "for some positive k" is clearer than "∃ k > 0" or"for every fixed positive number k" is clearer than "∀ k>0"? How do you feel about ? (following Positive real numbers) (2) The citation dump is because horizontal space is limited, I had them per-formula before but there's not much room there. (Maybe that wasn't the issue with the table though?) (4) As Sapphorain mentioned, the notations and are from the paper "Big Omega versus the wild functions", page 6. I don't feel strongly about them; it does seem like the notation is limited to that section of that paper. (3) The paper also has a line diagram ordering the various notations, which is where I created the phrase "smallest to largest" (i.e., left to right on said diagram). <, = >, etc. are discussed in several places in the paper. ~ and ≈ aren't in there but Knuth mentions that ~ is a subset of Big Theta, so I think the approximation notation is reasonable ( is usually used for a "loose sense" of equality; technically I guess might be more appropriate, as on page 2 Prinsheim is said to have used it for ~, but whatever). --Mathnerd314159 (talk) 23:37, 14 March 2017 (UTC)


In response to this edit summary by Sapphorain: the citation is to an article from 1951; presumably 25 = 1976 - 1951. Since Hardy and Littlewood were using their definition in 1914, this is incredibly silly. Since the citation predates Knuth, the cited article can't be addressing his claim, so it can't support "however" anything. This is just some editor writing in their own personal rebuttal to Knuth. But it is also a nonsequitur in that it does not address the substance of Knuth's claims. I would like to re-remove it. --JBL (talk) 23:09, 14 March 2017 (UTC)

The citation is not to some article, but to Titchmarsh's textbook on the Riemann zeta function, published in 1951, and which is in the private library of every mathematician working in analytic number theory. Titchmarsh makes frequent use in it of the symbol Omega, and this just proves that Knuth was wrong in his assertion. That's all. This is not non sequitur, and this is not silly: it deserves to be mentioned. Sapphorain (talk) 23:19, 14 March 2017 (UTC)
If you replace the word "article" in my post with "book" it does not change the substance, which you have not really responded to. Knuth's statement is 100% consistent with "this notation is used in a textbook in 1951." Indeed, it is consistent even with "this notation is commonly understood by analytic number theorists." If you would like to attach a WP policy to the words "silly nonsequitur," it is WP:SYNTH -- you will notice that it is not possible to rewrite this sentence in a way that would pass synth because there is no secondary source here. --JBL (talk) 23:32, 14 March 2017 (UTC)
I just don't understand what you say. Knuth's assertion that "their definition is by no means in wide use" is clearly contradicted by the content of Titchmarsh's book. I think you are commenting on a subject you are not familiar with. Sapphorain (talk) 23:48, 14 March 2017 (UTC)
That something is used among analytic number theorists is completely compatible with it not being "in wide use." The number of analytic number theorists is very small, in absolute terms and even as a fraction of the mathematical community. But even if I accepted 100% the position that Knuth was completely in the wrong as a substantive matter, the sentence is both extremely silly as written (because 1914 < 1951) and a clear case of synth. --JBL (talk) 23:56, 14 March 2017 (UTC)
JBL is applying the rules correctly. We can't add our own disproofs of sources. In order to get this into the article we need (1) a reliable source making the point you want to make, (2) an argument that the point satisfies WP:DUE and other content requirements. McKay (talk) 03:14, 15 March 2017 (UTC)
I rephrased the mention of Titchmarsh's book. Sapphorain (talk) 07:31, 15 March 2017 (UTC)