Why is Radix Sort $O(n)$?

In radix sort we first sort by least significant digit then we sort by second least significant digit and so on and end up with sorted list.

Now if we have list of $n$ numbers we need $\log n$ bits to distinguish between those number. So number of radix sort passes we make will be $\log n$. Each pass takes $O(n)$ time and hence running time of radix sort is $O(n \log n)$

But it is well known that it is linear time algorithm. Why?

• This is why linear time sorts usually require that the input be integers over some fixed range. Radix sort requires a fixed range on the digits. In your example you assumed that the range was $[0,1]$, but any integer range is possible for the digits; for example, you could have chosen $[0, \sqrt{n}]$ – Joe Oct 11 '12 at 23:55

if we have a list of $n$ numbers we need $\log n$ bits

No: if we have a list of numbers between $0$ and $2^k - 1$, we need $k$ bits. There is no relationship between $k$ and $\log n$ in general.

If the numbers are all distinct, then $\log n \ge k$, and radix sort on distinct numbers therefore has a time complexity of $\Omega(n \log n)$. In general, the complexity of radix sort is $\Theta(n \, k)$ where $n$ is the number of elements to sort and $k$ is the number of bits in each element.

To say that the complexity of radix sort is $O(n)$ means taking a fixed bit size for the numbers. This implies that for large enough $n$, there will be many duplicate values.

There is a general theorem that an array or list sorting method that works by comparing two elements at a time cannot run faster than $\Theta(n \log n)$ in the worst case. Radix sort doesn't work by comparing elements, but the same proof method works. Radix sort is a decision process to determine which permutation to apply to the array; there are $n!$ permutations of the array, and radix sort takes binary decisions, i.e. it decides whether to swap two elements or not at each stage. After $m$ binary decisions, radix sort can decide between $2^m$ permutations. To reach the $n!$ possible permutations, it is necessary that $m \ge \log (n!) = \Theta(n \log n)$.

An assumption in the proof that I did not write out above is that the algorithm must work in the case when the elements are distinct. If it is known a priori that the elements are not all distinct, then the number of potential permutations is less than the full $n!$. When sorting $k$-bit numbers, it is only possible to have $n$ distinct elements when $n \le 2^k$; in that case, the complexity of radix sort is indeed $\Omega(n \log n)$. For larger values of $n$, there must be collisions, which explains how radix sort can have a complexity that's less than $\Theta(n \log n)$ when $n \gt 2^k$.

• An alternative point of view is that of the word-RAM cost model: Our machine can work with integers of $w$ bits in constant time. (Current machines having $w=64$.) That way, one step of distribution sort with $2^w$ buckets can be done in $O(1)$ time by directly accessing a corresponding array element. That way, radix sort is linear for $n$ integers of $w=O(\log n)$ bits each. – Sebastian Mar 25 '14 at 11:26

Be careful with your analysis: what do you assume to make sorting run in $O(n)$ time? This is because each of your digits are in a range from $0$ to $k-1$, meaning your digits can take on $k$ possible values. You need a stable sorting algorithm, so you can for example choose counting sort. Counting sort runs in $\Theta(n+k)$ time. If $k=O(n)$, counting sort runs in linear time.

Each one of your strings or numbers have $d$-digits. As you say, you make $d$ passes over them. Hence, radix sort clearly runs in $\Theta(d(n+k))$ time. But if we consider $d$ to be constant and $k=O(n)$, we see that radix sort runs in linear time.

• For example, suppose that you are sorting integers in the range $[0, N-1]$ for some $N = O(n^d)$ for constant $d$. Then you can have $O(d)$ digits each with range $O(n)$. – Joe Oct 11 '12 at 23:53

I think the assumption $k = \log_2(n)$ is wrong. You can perform radix sort with numbers in, e.g., hex. Thus, at each step you split you array of numbers into $16$ buckets.

• As far as big-O is concerned, there's no difference between $\log_2n$ and $\log_{16}n$. – Rick Decker Jan 30 '15 at 20:03