Content deleted Content added
→Usage of bigO notation. "At least O(...)": Don't use Ω() when it is not a clear lower bound |
|||
Line 636:
[[User:Syrak|Syrak]] ([[User talk:Syrak|talk]]) 22:49, 16 November 2015 (UTC)
: I've [https://en.wikipedia.org/w/index.php?title=Sorting_algorithm&diff=693162779&oldid=693146372|reverted Qwertyus] replacing the Ω() bound in favor of O(n).
: Higher up in that section, the best average/worst case performance is described as O(nlogn).
:: These are all [[comparison sort]]s, and so cannot perform better than {{math|O(''n'' log ''n'')}} in the average or worst case.
: There are strange scope of quantification issues.
: Saying a sorting algorithm is O(nlogn) allows the execution with particular input to be less than nlogn; bubble sort doing O(n) is not a surprise.
: Some algorithms are strictly Θ(nlogn). Heapsort goes through all the motions no matter what. But that doesn't mean all sorting has such a lower bound.
: Saying a sorting algorithm is &Omega(nlogn) says it can never do better than nlogn. Bubblesort does better once in a while.
: Throwing in "average case" or "worst case" muddies an order statistic.
: Speaking of Ω() in the context of "worst case" is really speaking in terms of an upper bound (the worst case) rather than a lower bound.
: The meaning of "average case" for many sorts is the same as "worst case". Yes, I know quicksort's worst case is a counterexample to that statement.
: I don't see Ω() have the precision claimed.
: [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 21:13, 30 November 2015 (UTC)
| |||