Complexity of Radix Sort

Question

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

Answer 1

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.