Question 46
Counting Sort achieves linear O(n + k) running time under which specific condition?
Counting Sort counts key occurrences in a frequency array of size k, running in O(n + k) linear time when $k = O(n)$. Counting sort is non-comparison-based and uses a count array indexed by key values. Its O(n+k) bound is useful when the key range k is not excessively larger than n.