If there are n integers to sort, each integer had d digits and each digit is…
2015
If there are n integers to sort, each integer had d digits and each digit is in the set {1,2,…,𝑘}, radix sort can sort the numbers in :
- A.
\(O(d \: n \: k)\) - B.
\(O(d \ n^k)\) - C.
\(O(d+n)k)\) - D.
\(O(d(n+k))\)
Attempted by 129 students.
Show answer & explanation
Correct answer: D
Key idea: Radix sort processes the numbers digit by digit and uses a stable sorting algorithm (commonly counting sort) on each digit.
Number of passes: d (one stable sort per digit).
Cost per pass: counting sort runs in O(n + k) because it counts frequencies over the k possible digit values and then places the n items accordingly.
Total time: Multiply the number of passes by the cost per pass: d × O(n + k) = O(d (n + k)).
Notes: If k = O(n), the complexity becomes O(d n). If d is a constant, the complexity is O(n + k).