Multiple choice technology

What is the best possible running time of the code to sort a list of n numbers given the maximum number (k) of the list.

  1. O(n+k)

  2. O(lgk+n)

  3. O(klgn+n)

  4. O(nlgk+n)
Reveal answer Fill a bubble to check yourself
A Correct answer
Explanation

When the maximum value k in the list is known, we can use counting sort which runs in O(n+k) time - O(n) to count occurrences and O(k) to output sorted values. This is better than comparison-based sorts like merge/quick sort which require O(n log n) in the best case.

Keep practicing — related questions