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.
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