If the range k significantly exceeds the number of elements n, Counting Sort's space complexity becomes a concern, typically at O(k), making it less efficient due to increased space requirements. Conversely, in practical scenarios where the range k is much smaller than n, Counting Sort tends to operate efficiently, approaching O(n).