I am a little confused by the complexity proof of Radix Sort.

For counting sort, the complexity reported is $$O(n+R)$$, where $$n$$ is the number of items and $$R$$ is the range.

But this is not entirely correct, right? To do binary arithmetic on numbers as big as $$R$$, I need $$\log_2 R$$ operations for any deterministic hashing function. So the complexity of counting shot should be $$O(\log_2 R \cdot (n+R))$$.

Then the complexity of radix sort with base $$b$$ should be $$O(\log_b R \cdot \log_2b \cdot (n+b))$$, which is equivalent to $$O(\log_2R \cdot n)$$. For range $$R = \Omega(n)$$, this is $$\Omega(n \log n)$$ and thus not $$O(n)$$.

Can someone point out where I am going wrong in my proof? As far as I know, radix sort is $$O(n)$$ for $$R = O(n^c)$$.

• You can use Mathjax here. See: math.meta.stackexchange.com/questions/5020/… Sep 30 '20 at 4:34
• Thanks, I didn't realize that was enabled on this stack exchange.
– xyz
Sep 30 '20 at 21:49

We typically analyze algorithms in the so-called "RAM machine" or "transdichotomous model". In this model, operations on machine words take $$O(1)$$, and a machine word has length $$O(\log n)$$ bits, where $$n$$ is the size of the input (in bits), or any other polynomially related quantity.
If $$R$$ is polynomial in $$n$$ (in this case, the length of the array), then an integer in the range $$\{1,\ldots,R\}$$ can be stored in a single machine word, and so operations on such integers take constant time in this model.
• Arbitrary precision arithmetic doesn't necessarily take $O(1)$, even in the transdichotomous model. The basic operations allowed by the model operate on machine words. Sep 30 '20 at 21:50
• If $n < 2^{64}$ and $R = O(n^c)$ then radix sort is $O(1)$. Sep 30 '20 at 21:53
• A machine word is defined in the transdichotomous model as a word of length $O(\log N)$ bits, where $N$ is the input size in bits. Sep 30 '20 at 21:54
• Real-world machines can only access $O(1)$ memory, so any algorithm takes $O(1)$. This improves on your $O(n\log n)$. Sep 30 '20 at 21:57