Radix sort can sort n integers in O(n) time despite the Ω(n log n) lower bound because
Ait uses parallelism on multi-core CPUs
BΩ(n log n) applies to comparison sorts; radix reads digits directly
Cthe inputs are restricted to already-sorted permutations
Dn log n grows slower than n for small inputs
Answer & Solution
Correct answer: B. Ω(n log n) applies to comparison sorts; radix reads digits directly
The Ω(n log n) lower bound assumes the only way the sort distinguishes elements is by comparing them pairwise. Radix sort reads the actual bit or digit representation and uses it as a bucket index. That extra information lets it run in O(n × k) where k is the number of digits, which is O(n) when k is constant.
Related questions
An NP-hard problem differs from an NP-complete one because NP-hard problemsThe first problem proved to be NP-complete wasA problem X is NP-complete if and only ifWhy does theoretical computer science draw the line at 'polynomial-time' for tractability?Which set inclusion is established (i.e., proven, not open)?The class NP is the set of decision problems for whichFloyd-Warshall detects the presence of a negative cycle byTopological sort is well-defined for