Latest revision as of 01:05, 28 September 2021

Internal

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.

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 (view source) Ovidiu (talk \| contribs) (→‎Overview) ← Older edit		Latest revision as of 01:05, 28 September 2021 (view source) Ovidiu (talk \| contribs) (→‎Theorem)
Line 14:		Line 14:
	=Theorem=		=Theorem=

	Every comparison-based sorting algorithm has worst-case running time Ω(n log n). We assume deterministic but lower bound extends to randomized.		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.