Counting Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Counting Sort Algorithm

O(n + k)

Understanding Time Complexity

Counting Sort is a special sorting method that works well when numbers are in a small range.

We want to understand how the time it takes grows as the list size and number range grow.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function countingSort(arr) {
  const max = Math.max(...arr);
  const count = new Array(max + 1).fill(0);
  for (const num of arr) {
    count[num]++;
  }
  let sortedIndex = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i] > 0) {
      arr[sortedIndex++] = i;
      count[i]--;
    }
  }
  return arr;
}
    

This code sorts an array 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: Counting each number in the input array and then rebuilding the sorted array.
• How many times: The first loop runs once for each element in the input (n times). The second loop runs once for each number in the range (k times), and inside it, the inner loop runs as many times as the count of that number.

How Execution Grows With Input

Explain the growth pattern intuitively.

Input Size (n)	Range Size (k)	Approx. Operations
10	5	About 10 + 5 = 15 operations
100	20	About 100 + 20 = 120 operations
1000	100	About 1000 + 100 = 1100 operations

Pattern observation: The time grows roughly with the sum of the input size and the range size.

Final Time Complexity

Time Complexity: O(n + k)

This means the time grows linearly with both the number of items and the range of numbers.

Common Mistake

[X] Wrong: "Counting Sort always runs in linear time regardless of the number range."

[OK] Correct: If the range of numbers (k) is very large compared to the input size (n), the time depends on k too, so it can be slower.

Interview Connect

Understanding Counting Sort's time complexity helps you choose the right sorting method based on data size and range, a useful skill in real coding tasks.

Self-Check

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