alleryStart learning →Counting sort runs in
AO(n log n) like any comparison-based sort
BO(n²) on already-sorted inputs
CO(n + r) where r is the range of possible key values
DO(log n) using a balanced binary search tree
Answer & Solution
Correct answer: C. O(n + r) where r is the range of possible key values
Counting sort tallies each distinct value, then prefix-sums to place elements.
It examines each of n elements once (O(n)) and walks the count array of size r (O(r)). Total O(n + r).
When r is small (scores 0..100), this beats any comparison sort.
When r is large (e.g., 2^32), counting sort becomes useless.
Keep practising Algorithms
Browse all Algorithms questions for GATE CSE, or explore more Computer Science topics.