Content deleted Content added
→Usage of bigO notation. "At least O(...)": try to clarify my comment |
|||
Line 655:
::This is exactly the bound we're trying to express: no algorithm can beat an {{math|''n'' log ''n''}} lower bound in its worst case. 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.
::Our current formulation is in fact 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)
::: (e/c) I don't dispute that a sorting algorithm requires k * (nlogn) comparisons in the worst case.
::: I dispute that makes the algortithm complexity Ω(nlogn).
::: The CT definition of Ω() does not have the notion of worst case in it. It says that for all possible inputs, the lower bound cannot be beaten. ∀ inputs is not the same as ∃ a worst case input.
::: Quicksort requires n<sup>2</sup> comparisons in the worst case; would we then say that quicksort is Ω(n<sup>2</sup>)?
::: It's true in the worst case, but it doesn't seem right to me. I don't like putting quantification monikers on order statistics that have lower and upper bounds built into them.
::: To put it another way, I can use Ω(), Θ(), and O() to characterize heap and bubble sort:
:::: Heap sort: Θ(nlogn)
:::: Bubble sort: Ω(n) and O(n<sup>2)
::: Those statements make sense as complexity theory lower (best case) and upper (worst case) bounds.
::: 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).
::: Perhaps the best way out is to avoid order notaiton and just say comparison sorts require at least nlogn comparisons for some inputs.
::: [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 23:25, 30 November 2015 (UTC)
| |||