snippetMajor
Why is Radix Sort $O(n)$?
Viewed 0 times
sortwhyradix
Problem
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?
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?
Solution
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 \le 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 all $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$.
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 \le 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 all $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$.
Context
StackExchange Computer Science Q#5030, answer score: 22
Revisions (0)
No revisions yet.