If there are n integers to sort, each integer has d digits, and each digit is…
2016
If there are n integers to sort, each integer has d digits, and each digit is in the set {1, 2, …, k}, radix sort can sort the numbers in :
- A.
O (k (n + d))
- B.
O (d (n + k))
- C.
O ((n + k) l g d)
- D.
O ((n + d) l g k)
Attempted by 114 students.
Show answer & explanation
Correct answer: B
Answer: O (d (n + k))
Reasoning:
Key insight: Radix sort sorts by processing each digit position using a stable linear-time sort (commonly counting sort).
Per-digit cost: Counting sort on n items with k possible digit values takes O(n + k) time.
Repeat for d digits: Total time = d × O(n + k) = O(d (n + k)).
Notes: If k = O(n), this simplifies to O(d n). There is no logarithmic factor in d or k in the standard radix sort analysis.