Question

I was trying to analyze radix sort in terms of time and space. Assume that we are given $n$ 32-bit integers which we would want to sort by looking at the least significant digits first.

$k$ is the total amount of bits that you will be working with at every step. So at first you look at the first $k$ bits, and sort the elements with counting sort. Then you look at the next $k$ bits etc.

In total we would have to run counting sort $\frac{32}{k}$ times. In the counting sort phase we will both have to scan the input array and also the bucket array, where the input array is of size $n$ and the bucket array is of size $2^k$. In other words the running time is going to be $ \Theta (\frac{32}{k}(n+2^k))$. As for space, we will need an extra temporary array of size $n$ during the counting sort phase, and also an array for the bucket, so in total the space will be $\Theta (2n + 2^k)$

So we have:

Time: $ \Theta (\frac{32}{k}(n+2^k))$

Space: $\Theta (2n + 2^k)$

Am I the only one who can't see why this is $O(n)$?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top