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.


Near the end of the section titled Little-o notation the right facing "U" is used as follows:

o ( f ) ⊂ O ( f ) {\displaystyle o(f)\subset O(f)} o(f)\subset O(f) (and thus the above properties apply with most combinations of o and O).

However the Set (mathematics) page under Subsets says,

"The expressions A ⊂ B and B ⊃ A are used differently by different authors; some authors use them to mean the same as A ⊆ B (respectively B ⊇ A), whereas others use them to mean the same as A ⊊ B (respectively B ⊋ A)."

So what exactly does ⊂ mean as used in this page?


29Flavors (talk) 21:01, 12 December 2017 (UTC)

Good point 29Flavors. The containment is strict except in some uninteresting degenerate cases; but the use of this notation is nonstandard and not helpful. I've now cleaned up the little-o section substantially. (I hope you will forgive me for replacing the ref tags with a direct wikilink in your comment.) --JBL (talk) 22:34, 12 December 2017 (UTC)