Practice question · Multiple choice
Comparison-based sorting cannot beat O(n log n), and counting sort runs in O(n). Why is that not a contradiction?
Hints
- Ask what information counting sort uses about each element.
- The bound has a qualifier in its name. What does it exclude?
Show the answer
A. Because counting sort never compares elements; it indexes by value.
Why
The theorem bounds comparison-based sorting, by a counting argument: n! orderings, one bit per comparison, so log₂(n!) ≈ n log n comparisons are needed. Counting sort never compares, it uses values as indices, which is more information than a comparison gives. The assumption is also the limitation: it needs bounded integer keys, and its cost is O(n + k) in the range.
Practise Sorting Strategies
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Sorting Strategies
- Order the steps of one round of selection sort.
- Stability in a sort, preserving the order of equal elements, sounds like a technicality. When does it become…
- Sorting stability only matters when the records carry information beyond the key being sorted on.
- Sort each sorting algorithm by its typical asymptotic cost.
- Match each sort to its distinguishing property.