Content deleted Content added
Line 677:
::::Just a little comment about "at least nlogn comparisons" suggestion. This just doesn't work, because actually it is "at least Cnlogn comparisons" where C is unknown constant. So to say number of operations is proportional to nlogn in worst case scenario (rather than bounded by this exact number), which basically is the meaning on O(nlogn) notation. [[User:Trimutius|Trimutius]] ([[User talk:Trimutius|talk]]) 14:57, 3 December 2015 (UTC)
:::*If the lower bound of a comparison sort is <math>n \log n</math> comparisons, but the article says <math>O(n \log n)</math>, then one could, for example, infer that a comparison sort that only requires <math>2n</math> comparisons exists, because <math>2n \leq 2(n \log n) \text{ for all } n \geq 2</math> (see {{Doi|10.1145/1008328.1008329}}). <math>\Omega</math> notation would be appropriate; such an algorithm would not pass because <math>(\exists k:2n \leq c(n \log n) \text{ for all } n \geq k)</math>, no matter how close c is to 0 (also see same page). '''''[[User:Esquivalience|<span style="color: #33BBFF; font-family:Lato, monospace'">Esquivalience</span>]]'' <sup>[[User talk:Esquivalience|<span style="color:#00B88A;">t</span>]]</sup>''' 22:29, 16 February 2016 (UTC)
| |||