Chapter 49: DSA Radix Sort Time Complexity
DSA Radix Sort Time Complexity Let’s understand this topic very clearly and step-by-step, like I’m sitting next to you with a notebook, writing down every part, counting operations together, giving realistic numbers, and explaining honestly why the time complexity is what it is — and when Radix Sort becomes extremely fast or surprisingly slow.
1. Quick reminder — What Radix Sort actually does
Radix Sort is not a comparison-based sort. It sorts numbers digit by digit, starting from the least significant digit (rightmost) to the most significant digit (leftmost).
For each digit position:
- It uses a stable sorting subroutine (usually Counting Sort) to sort all numbers based on that digit only.
- Because Counting Sort is used, and it is stable, the relative order from previous passes is preserved.
2. The time complexity formula everyone should remember
Total time complexity = O(d × (n + k))
Where:
- n = number of elements in the array
- d = number of digits in the largest number (maximum length of numbers)
- k = number of possible digit values (usually 10 for decimal numbers, i.e., 0–9)
Most common practical case (decimal numbers) → k = 10 (constant) → Time = O(d × n)
3. Why is it O(d × n) ? (very detailed breakdown)
Let’s see what happens in one complete pass (one digit position):
- Counting phase — count frequency of each digit (0–9) → Loop over all n elements → O(n)
- Cumulative count / position calculation → Loop over 10 buckets → O(10) = O(1)
- Building output array (stable placement) → Loop over all n elements backward → O(n)
So one digit position takes O(n + 10) ≈ O(n) time
Now — how many such digit positions are there?
d = number of digits in the largest number Examples:
- All numbers ≤ 999 → d = 3
- All numbers ≤ 999,999 → d = 6
- All numbers ≤ 2³¹–1 (≈ 2 billion) → d = 10
- All numbers ≤ 10¹⁸ → d = 18–19
So total time = d × O(n) = O(d × n)
4. Very Realistic Examples with Numbers
Example 1 – Small range (very common case)
n = 1,000,000 elements Numbers between 0 and 999,999 → d = 6
Time = O(6 × 1,000,000) ≈ 6 million operations → Extremely fast (usually < 0.1 seconds)
Example 2 – Typical 32-bit integers
n = 1,000,000 elements Numbers between -2³¹ and 2³¹–1 → after shifting to positive → d ≈ 10
Time = O(10 × 1,000,000) ≈ 10 million operations → Still very fast
Example 3 – Very large numbers (bad case)
n = 100,000 elements Numbers have up to 100 digits (very large integers, e.g., big integers)
Time = O(100 × 100,000) = 10 million operations → Still acceptable, but notice that time now depends heavily on d
Example 4 – Worst realistic case
n = 1,000,000 Numbers up to 10¹⁸ (18–19 digits)
Time ≈ 18–19 million operations → Still fast, but you can see that d starts to matter
5. Comparison Table – Radix Sort vs Other Sorts
| Algorithm | Best Case | Average Case | Worst Case | Space | Stable? | When it wins |
|---|---|---|---|---|---|---|
| Radix Sort | O(d n) | O(d n) | O(d n) | O(n + k) | Yes | Small d (d << n) |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | General case |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stability needed |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(n + k) | Yes | Very small k |
Key observation:
Radix Sort is linear in n as long as d is small It is one of the few sorting algorithms that can beat the O(n log n) lower bound of comparison-based sorts when d is small.
6. Summary – What to say in interviews
“Radix Sort has O(d × n) time complexity, where n is the number of elements and d is the number of digits in the largest number (or more generally, the number of passes needed). Since k = 10 (for decimal digits) is constant, the time complexity simplifies to O(d × n). When d is small compared to n (for example, 32-bit or 64-bit integers where d ≈ 10), it becomes effectively linear O(n) time — faster than any comparison-based sort. However, if d is very large (for example, very big integers with hundreds of digits), the time becomes O(d × n) and can be slower than O(n log n) algorithms. Space complexity is O(n + k) — usually O(n) in practice.”
7. Quick Cheat Sheet – Radix Sort Time Complexity
| Question | Answer |
|---|---|
| Time complexity (general) | O(d × (n + k)) |
| Time complexity (decimal numbers) | O(d × n) |
| Best / Average / Worst case | All same — O(d × n) |
| Space complexity | O(n + k) (usually O(n)) |
| Stable? | Yes |
| When it is fastest | When d is small (e.g., 32-bit/64-bit integers) |
| When it is slow | When d is very large (big integers, very long strings) |
Do you want to go deeper into any part?
Very common follow-up questions:
- Why is Radix Sort stable while Quick Sort is not?
- How to handle negative numbers in Radix Sort?
- Radix Sort vs Counting Sort — when to use which
- Mathematical explanation why it’s O(d n)
- Radix Sort on strings (when k = 256 for ASCII)
Just tell me which direction you want — I’ll continue explaining in the same detailed, calm, teacher style with clear examples 😊
