Content deleted Content added
→Usage of bigO notation. "At least O(...)": sorry; I'm not in good shape right now |
→Usage of bigO notation. "At least O(...)": cite CLRS |
||
Line 650:
: I don't see Ω() having the precision claimed.
: [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 21:13, 30 November 2015 (UTC)
::[[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)
| |||