Question

If we use Radix Sort to sort n integers in the range $(n^{k/12},n^k$), for some k > 0 which is independent of n, the time taken would be

• A. $\Theta \left(nlogn\right)$
• B. $\Theta \left(n^2\right)$
• C. $\Theta \left(n\right)$
• D. $\Theta \left(kn\right)$

Answer 1

The correct option is D $\Theta \left(kn\right)$

Time complexity of radix sort $\Theta \left(kn\right)$