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.


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)