What is the time complexity of counting sort for n integers whose values lie in the range 0 to k?
Correct answer B. O(n + k)
Explanation
Counting sort tallies how often each value occurs in an array of size k + 1, converts the tallies into positions and places each element directly, so the work is proportional to n + k. It makes no comparisons, so the Ω(n log n) comparison-sort lower bound does not apply. It is efficient only when k is not much larger than n.
Answer checked How we write and check questions
Discussion