Radix Sort Algorithm in DSA Javascript - Time & Space Complexity

Time Complexity: Radix Sort Algorithm

O(d x n)

Understanding Time Complexity

Radix Sort sorts numbers by processing digits one at a time. Understanding its time complexity helps us see how it handles larger lists efficiently.

We want to know how the number of steps grows as the list and number size increase.

Scenario Under Consideration

Analyze the time complexity of the following Radix Sort code snippet.

function radixSort(arr) {
  const maxNum = Math.max(...arr);
  let digitPlace = 1;
  while (digitPlace <= maxNum) {
    const buckets = Array.from({ length: 10 }, () => []);
    for (const num of arr) {
      const digit = Math.floor((num / digitPlace) % 10);
      buckets[digit].push(num);
    }
    arr = [].concat(...buckets);
    digitPlace *= 10;
  }
  return arr;
}
    

This code sorts an array of numbers by grouping them digit by digit from least to most significant.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over all numbers for each digit place.
• How many times: Once per digit place, which depends on the maximum number's length.

How Execution Grows With Input

Each digit place requires scanning all numbers once. More numbers mean more work per digit. More digits mean more passes.

Input Size (n)	Approx. Operations
10 (digits = 2)	~20 (10 numbers x 2 digits)
100 (digits = 3)	~300 (100 numbers x 3 digits)
1000 (digits = 4)	~4000 (1000 numbers x 4 digits)

Pattern observation: Operations grow linearly with number count and digit length combined.

Final Time Complexity

Time Complexity: O(d x n)

This means the time grows linearly with the number of items and the number of digits in the largest number.

Common Mistake

[X] Wrong: "Radix Sort is always faster than comparison sorts like Quick Sort."

[OK] Correct: Radix Sort depends on digit count and works best on fixed-length numbers. For large digit counts or non-integer data, comparison sorts may be faster.

Interview Connect

Understanding Radix Sort's time complexity shows you can analyze algorithms beyond simple loops. This skill helps you explain and choose sorting methods wisely.

Self-Check

"What if we changed the base from 10 to 2 (binary digits)? How would the time complexity change?"