Comparison Sorting Algorithms Complexity: Difference between revisions
Jump to navigation
Jump to search
| (2 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 | [[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.