6.21 Lower Bounds for Sorting
6.21 Lower Bounds for Sorting Lower bounds describe what no algorithm can beat under a given model. For sorting, the standard model is comparison-based sorting, where the algorithm learns order only by comparing elements. In this model, any algorithm must use at least on the order of ( n \log n ) comparisons in the worst case. Problem You want to understand the inherent cost of sorting and why many...