Comparison Sorting Algorithms Complexity: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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: comparison sorting cannot perform better than n lg n. The worst-case running time of a comparison algorithm is Ω(n lgn).


[[CLRS]] page 193.
[[CLRS]] page 193.


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

Revision as of 01:03, 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.