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

Time Complexity: Radix Sort Algorithm

O(d * n)

Understanding Time Complexity

We want to understand how the time taken by Radix Sort changes as the list size grows.

How does the number of steps grow when sorting more numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

void radixSort(int arr[], int n) {
    int maxVal = *max_element(arr, arr + n);
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        int output[n], count[10] = {0};
        for (int i = 0; i < n; i++)
            count[(arr[i] / exp) % 10]++;
        for (int i = 1; i < 10; i++)
            count[i] += count[i - 1];
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        for (int i = 0; i < n; i++)
            arr[i] = output[i];
    }
}
    

This code sorts an array of integers by processing digits from least to most significant.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop runs once per digit place (like ones, tens, hundreds).
• How many times: For each digit, it loops over the entire array multiple times to count and reorder.

How Execution Grows With Input

Execution grows with both the number of elements and the number of digits in the largest number.

Input Size (n)	Approx. Operations (for d digits)
10	About 10 x d steps
100	About 100 x d steps
1000	About 1000 x d steps

Pattern observation: The steps grow linearly with the number of elements and digits.

Final Time Complexity

Time Complexity: O(d * n)

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

Common Mistake

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

[OK] Correct: The time also depends on the number of digits (d), so if numbers have many digits, it takes longer.

Interview Connect

Understanding Radix Sort's time complexity helps you explain when it is efficient and how it compares to other sorting methods.

Self-Check

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