6
$\begingroup$

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)$?

$\endgroup$
15
$\begingroup$

You can choose $k = 1$ and then the time is $\Theta(32(n+2)) = \Theta(n)$ and the space is $\Theta(2n + 2) = \Theta(n)$. In general, if you replace 32 by any fixed number, the complexities will be $\Theta(n)$. If, however, you try to use radix sort with integers of non-constant width $m$, the complexities will be as stated (with $32$ replaced by $m$), or even worse, since you are assuming that operations on these integers take constant time, which might not be the case for integers of arbitrary size (depending on your computation model).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.