Content deleted Content added
→Usage of bigO notation. "At least O(...)": ... mind ... does ... not ... work ... today |
→Usage of bigO notation. "At least O(...)": point out imprecision |
||
Line 665:
:::* Bubble sort: Ω(n) and O(n<sup>2</sup>)
::: Those statements make sense as complexity theory lower (best case) and upper (worst case) bounds. And I don't have to add "best" or "worst" monikers.
::::If you want to be precise, you do. Heap sort is also Ω(n) and O(n<sup>2</sup>) because Θ(nlogn) is within those bounds. A precise statement would be that bubble sort is Θ(n<sup>2</sup>) in the worst case and Θ(n) in the best case. [[User:Qwertyus|Q<small>VVERTYVS</small>]] <small>([[User talk:Qwertyus|hm?]])</small> 08:23, 1 December 2015 (UTC)
::: In that context, a claim that comparison sorts are Ω(nlogn) is confusing.
::: I don't see the same confusion with a statement that a comparison sort cannot be better than O(nlogn).
| |||