Talk:Sorting algorithm: Difference between revisions

Revision as of 20:47, 17 February 2016

Revision as of 02:47, 18 February 2016

Line 687:

::: Well we should just think about what is important for sorts. Best cases of algorithms actually refer to Ω(f(n)), while worst cases refer to O(f(n)), and average case refers to some heuristics, which were made based on all possible inputs. But what is important for the algorithm is for it to be as fast as possible in worst possible case, so O(f(n)) is the only one in practical use for computer algorithms. And even though in tables we can mention that best cases are Ω(f(n)), this information is redundant and not relevant to the subject of the article. [[User:Trimutius|Trimutius]] ([[User talk:Trimutius|talk]]) 20:47, 17 February 2016 (UTC)

:::: The theorem does not state "the lower bound of a comparison sort is <math>n \log n</math> comparisons".

:::: We are interested in the order statistics of sorting algorithms.

:::: The notation has an shorthand connotation just like graph theory algorithms.

:::: Let '''n''' be an input sequence of ''n'' elements; ''f''('''n''') is the number of comparisons an algorithm needs to sort '''n'''. Shorthand is just ''f''(''n''), but realize that the shorthand ''f''(''n'') is not single valued.

:::: Given a particular algorithm, the meaning of [[Big O notation|O() and &Omega;()]] are clear. The first is an upper bound on the comparisons and second is a lower bound on the comparisons. There is no input sequence that will take more than O() comparisons and no input sequence that will take fewer than &Omega().

:::: The theorem states that for some input sequences (not necessarily all input sequences), a comparison sort will require some multiple of n log n comparisons.

:::: That means a comparison sorting algorithm cannot be better than O(n log n).

:::: If somebody claims to have an O(n) comparison sort, then we know they are wrong (or there's a mistake in the theorem).

:::: The theorem does NOT mean that all comparison sorts must be at least &Omega;(n log n).

:::: We know that the lowly bubble sort is &Omega;(n) because it will finish in n comparisons for sorted input sequences.

:::: Claiming a sort is &Omega;(n) does not violate the theorem.

:::: When another quantification ("in the worst case") is placed outside of the notation, it walks outside of the order statistic notation and butchers an interior quantifier.

:::: As it turns out, the order notation is inadequate for what you want to say here. It also adds confusion rather than clarifies.

:::: [[User:Glrx|Glrx]] ([[User talk:Glrx|talk]]) 02:47, 18 February 2016 (UTC)