Comparison Sorting Algorithms Complexity

Internal

• 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

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.