Comparison Sorting Algorithms Complexity: Difference between revisions
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 | |||
[[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.