Counting Sort Algorithm in DSA C++ - Time & Space Complexity

Time Complexity: Counting Sort Algorithm

O(n + k)

Understanding Time Complexity

We want to understand how the time needed by Counting Sort changes as the input size grows.

Specifically, how does the number of steps grow when sorting more numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void countingSort(int arr[], int n) {
    int maxVal = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > maxVal) maxVal = arr[i];
    }
    int count[maxVal + 1] = {0};
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    int index = 0;
    for (int i = 0; i <= maxVal; i++) {
        while (count[i]-- > 0) {
            arr[index++] = i;
        }
    }
}
    

This code sorts an array of integers by counting how many times each number appears, then rebuilding the sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Three loops: one to find the max value, one to count occurrences, and one to rebuild the sorted array.
• How many times: Each loop runs either n times (input size) or maxVal times (range of input values).

How Execution Grows With Input

The time grows with both the number of elements and the range of values.

Input Size (n)	Approx. Operations
10 (maxVal=5)	About 10 + 6 + 10 = 26 steps
100 (maxVal=50)	About 100 + 51 + 100 = 251 steps
1000 (maxVal=500)	About 1000 + 501 + 1000 = 2501 steps

Pattern observation: The steps grow roughly in proportion to n plus the range maxVal.

Final Time Complexity

Time Complexity: O(n + k)

This means the time depends on the number of elements n plus the range of values k.

Common Mistake

[X] Wrong: "Counting Sort always runs in linear time O(n)."

[OK] Correct: The time also depends on the range of input values k. If k is very large compared to n, the algorithm can be slower.

Interview Connect

Knowing how Counting Sort scales helps you choose the right sorting method for different data. This skill shows you understand trade-offs in algorithms.

Self-Check

"What if the input array contains negative numbers? How would the time complexity change?"