Revision as of 21:48, 30 November 2015 edit Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Usage of bigO notation. "At least O(...)": cite CLRS ← Previous edit		Revision as of 21:49, 30 November 2015 edit undo Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits m →Usage of bigO notation. "At least O(...)": ) Next edit →
Line 653: ::[[Introduction to Algorithms\|CLRS]], Theorem 8.1 (3rd ed., p. 193): :::Any comparison sort algorithm requires {{math\|Ω(''n'' log ''n'')}} comparisons in the worst case. ::So this is exactly the bound we're trying to express: no algorithm can have a worst case better than that. The theorem allows linear best cases (it doesn't concern them) and quadratic worst cases (since {{math\|''n''<sup>2</sup> {{=}} Ω(''n'' log ''n'')}}). [[User:Qwertyus\|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus\|hm?]])</small> 21:48, 30 November 2015 (UTC)

Talk:Sorting algorithm: Difference between revisions