Timeline for Complexity of Radix Sort
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 30, 2020 at 22:10 | comment | added | Yuval Filmus | The bit complexity model only allows operations on bits. It is non-uniform, in the sense that it allows different algorithms for each input size (though you can ask them to be uniform). This model is popular for analyzing algorithms in arithmetic, for example integer multiplication algorithms, though some people (e.g. Fürer) say that the transdichotomous model is a better fit. | |
| Sep 30, 2020 at 22:08 | vote | accept | xyz | ||
| Sep 30, 2020 at 22:08 | comment | added | xyz | Thank you. This is exactly what I was looking for! Just a followup. Are there any computational models that have finite word size but can access infinite memory? This encoding is certainly possible, you can always write the word size $w$ (for simplicity, multiple of 64 bits) for the rest of the input at the front of the input, then a special token. Then the rest of the input can be accessed as usual with this word size. | |
| Sep 30, 2020 at 21:57 | comment | added | Yuval Filmus | 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, 2020 at 21:57 | comment | added | Yuval Filmus | 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. | |
| Sep 30, 2020 at 21:55 | comment | added | xyz | True, I was abusing notation. In that case radix sort is indeed not $O(n)$, its $O(n\log n)$ for any finite word sized machine? | |
| Sep 30, 2020 at 21:54 | comment | added | Yuval Filmus | 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, 2020 at 21:53 | comment | added | Yuval Filmus | If $n < 2^{64}$ and $R = O(n^c)$ then radix sort is $O(1)$. | |
| Sep 30, 2020 at 21:53 | comment | added | xyz | So it would be correct to say that radix sort is $O(n)$ for $R = O(n^c)$ iff $n < 2^{64}$ (assuming 64-bit word size)? I didn't see this discussed in typical radix sort complexity proofs so I am unsure if I am doing the proof right. | |
| Sep 30, 2020 at 21:50 | comment | added | Yuval Filmus | 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, 2020 at 21:47 | comment | added | xyz | I am not sure I follow your logic, we can use multiple machine words to represent $n$ using arbitrary precision arithmetic right? So $n$ should be unbounded for analyses. | |
| Sep 30, 2020 at 7:08 | history | answered | Yuval Filmus | CC BY-SA 4.0 |