If we use Radix Sort to sort n integers in the range (nk/2,nk], for some k>0…
2008
If we use Radix Sort to sort n integers in the range (nk/2,nk], for some k>0 which is independent of n, the time taken would be?
- A.
Θ(n)
- B.
Θ(kn)
- C.
Θ(nlogn)
- D.
Θ(n2)
Attempted by 68 students.
Show answer & explanation
Correct answer: B
Key idea: pick the radix (base) to minimize the number of passes.
Upper bound on keys: the maximum value is n^k, so the number of digits in base n is log_n(n^k)=k.
Choose radix (base) b = n. Each counting-sort pass runs in Θ(n + b)=Θ(n + n)=Θ(n).
Number of passes is the number of digits d = k (a constant independent of n), so total time is Θ(d · n)=Θ(k · n)=Θ(n).
Note: If one used base 2 (bits) instead, the number of passes would be Θ(log n) and runtime Θ(n log n). However, radix sort allows choosing a larger base (such as n) to achieve linear time for this input range.