Comparison Sorting Algorithms Complexity: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
(Created page with "=Internal= * Sorting Algorithms =Overview= <font color=darkgray>TODO</font>")
 
 
(5 intermediate revisions by the same user not shown)
Line 3: Line 3:
* [[Sorting Algorithms#Comparison_Sort|Sorting Algorithms]]
* [[Sorting Algorithms#Comparison_Sort|Sorting Algorithms]]


=External=
* https://www.coursera.org/learn/algorithms-divide-conquer/lecture/P2uwC/omega-n-log-n-lower-bound-for-comparison-based-sorting-advanced-optional
=Overview=
=Overview=
<font color=darkgray>TODO: comparison sorting cannot perform better than n lg n. The worst-case running time of a comparison algorithm is Ω(n log n).


<font color=darkgray>TODO</font>
[[CLRS]] page 193.
 
</font>
 
=Theorem=
 
Every [[Sorting_Algorithms#Key_Comparison_Sorting_Algorithms|comparison-based sorting algorithm]] has worst-case running time Ω(n log n). We assume deterministic but lower bound extends to randomized.

Latest revision as of 01:05, 28 September 2021

Internal

External

Overview

TODO: comparison sorting cannot perform better than n lg n. The worst-case running time of a comparison algorithm is Ω(n log n).

CLRS page 193.

Theorem

Every comparison-based sorting algorithm has worst-case running time Ω(n log n). We assume deterministic but lower bound extends to randomized.