We have an array of N integers where each integer has at most K digits.
Accenture technical mcq question, verified with a worked answer. Free to practise - no sign-up.
We have an array of $N$ integers where each integer has at most $K$ digits. What is the time complexity of sorting the array using Radix Sort?
Show answer & explanation
Radix Sort processes each of the K digits independently, and for each digit position, it performs a counting sort pass over all N elements. Each pass takes O(N + R) time where R is the radix (typically 10 for decimal digits), which simplifies to O(N). Since there are K digit positions, the total time complexity is O(K * N). This is linear with respect to both the number of elements and the number of digits, making it more efficient than comparison-based sorts for certain inputs.
Step-by-step Derivation:
Radix Sort Algorithm Analysis:
- For each digit position i from 1 to K:
- Perform counting sort on all N elements based on digit i
- Counting sort takes O(N + R) where R = radix (e.g., 10)
- Simplified: O(N) per pass
- Total passes: K
- Total time complexity: K * O(N) = O(N * K)
Example with N=5 elements, K=3 digits:
- Pass 1 (units place): 5 operations
- Pass 2 (tens place): 5 operations
- Pass 3 (hundreds place): 5 operations
- Total: 3 * 5 = 15 = O(N * K) operations
Why other options are wrong:
- B) O(N log K): Incorrect; radix sort doesn't have a logarithmic relationship with K
- C) O(K log N): Incorrect; the N term is multiplicative, not logarithmic
- D) O(N²): Incorrect; radix sort is more efficient than quadratic algorithms