Content deleted Content added
Line 708:
: Phrases like "average time complexity of O(n log n)" just don't make sense, and there are at least couple of places where it states that. I'm against using Ω though, because that one isn't related to. We need some kind of alternative. For example just simply saying with words rather than notation: "average time complexity proportional to ''n''log''n''". Because that what people are basically trying to say.
:[[User:Trimutius|Trimutius]] ([[User talk:Trimutius|talk]]) 22:26, 19 February 2016 (UTC)
::I also agree that it would be best to state the theorem without using asymptotic notation; even TAOCP tends to avoid it:
{{Tmbox|image=none|text=
'''The best worst case.''' The first problem that arises naturally is to find comparison trees that minimize the maximum number of comparisons made. (Later we shall consider the average number of comparisons.) Let S(n) be the minimum number of comparisons that will suffice to sort n elements. If all the internal nodes of a comparison tree are at levels < k, it is obvious that there can be at most 2k external nodes in the tree. Hence, letting k = S(n), we have <math>S(n) \geq \lceil \log n \rceil</math>. Stirling's approximation tells us that <math>\lceil \log n! \rceil = n \log n - n / \ln 2 - \frac{1}{2} \log n + O(1)</math>, hence roughly <math>n \log n</math> comparisons are needed. <br />
:– [[The Art of Computer Programming|TAOCP]] § 5.3.1 (Sorting and Searching)}}
::A possible replacement is (ref is TAOCP chapter 5): <blockquote>The number of comparisons required by a comparison sorting algorithm is roughly [[Proportionality|proportionate]] to n log n comparisons in the worst case; in better cases, comparison sorting can be performed in at most a multiple of n comparisons.</blockquote> -'''''[[User:Esquivalience|<span style="color: #33BBFF; font-family:Lato, monospace'">Esquivalience</span>]]'' <sup>[[User talk:Esquivalience|<span style="color:#00B88A;">t</span>]]</sup>''' 02:05, 6 March 2016 (UTC)
| |||