Revision as of 21:58, 30 November 2015 edit Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Usage of bigO notation. "At least O(...)": imprecision of current statement ← Previous edit		Revision as of 21:59, 30 November 2015 edit undo Qwertyus (talk \| contribs) Extended confirmed users 31,640 edits →Usage of bigO notation. "At least O(...)": overindented Next edit →
Line 654: :::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'')}}). CLRS don't say much about the average case, except giving it as an exercise to proof that linear average case is impossible. :::The current formulation is imprecise. A linear time algorithm still runs in {{math\|''O''(''n'' log ''n'')}}, so in that sense it doesn't perform any better. [[User:Qwertyus\|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus\|hm?]])</small> 21:58, 30 November 2015 (UTC)

Talk:Sorting algorithm: Difference between revisions