Talk:Sorting algorithm: Difference between revisions

Revision as of 21:18, 30 November 2015

Revision as of 21:19, 30 November 2015

Line 644:

: Saying a sorting algorithm is O(nlogn) allows the execution with particular input to be less than nlogn; bubble sort taking n comparisons is not a surprise; it does not contradict the bound.

: 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 Ω(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.