4 ms·
>https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort >However, in general w cannot be considered a constant: if all n keys are di
by micahbright 9y ago
>https://en.wikipedia.org/wiki/Radix_sort https://en.wikipedia.org/wiki/Radix_sort
>However, in general w cannot be considered a constant: if all n keys are distinct, then w has to be at least log n
We can't ignore the log n, unless the number of distinct elements is small with respect to n. Since this wouldn't be known a priori, we can't make that assumption.
Also, note that if we know, a priori, that the number of distinct elements is small wrt N, we can simply use the hash set for O(N) without any of the problems he goes to outline in the article.
- rocqua 9y agoOP actually addressed the w from wikipedia. He calls it the size of the objects k. The point being, run-time remains proportional to the actual in-memory size of whatever you are trying to count. Heck, for the example of 64 bit integers, w is fixed at 64. Note also that the quote from Wikipedia concerns distinct elements. It is rather inherent to the problem we are solving that not all elements are distinct.
- micahbright 9y agoIt still doesn't improve any on a quick-sort because quicksort is going to run in O(nlog n)=O(n64)=O(N) as well. So what's the point?
- contravariant 9y agoIt's hardly fair to assume you can compare two k-bit objects in O(1), logically it should be at least O(k) (got to read every bit at some point). Which would make quicksort O(k n log n) rather than radix sort's O(k n).
- rocqua 9y agoFor the quick-sort case, log n need not be 64. That presumes no duplicates. In the problem to be solved. duplicates matter. Now, in practice it seems unlikely that more than 2^64 integers will need to be sorted, but for the rigor of asymptotic notation, you need to consider that case. I'd like to add that the tree-structure needed for radix sort is going to make it useless in practice. Trees are essentially synonymous with cache-misses.