1
$\begingroup$

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

$\endgroup$
2

1 Answer 1

Reset to default
3
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:50
  • 1
    $\begingroup$ If $n < 2^{64}$ and $R = O(n^c)$ then radix sort is $O(1)$. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:53
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:54
  • 1
    $\begingroup$ If the word size is fixed, then we're in the bit complexity model. It is less useful than the transdichotomous model to predict the behavior of actual algorithms. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:57
  • 1
    $\begingroup$ Real-world machines can only access $O(1)$ memory, so any algorithm takes $O(1)$. This improves on your $O(n\log n)$. $\endgroup$
    – Yuval Filmus
    Sep 30, 2020 at 21:57

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.