4 ms·
OP 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 o
by rocqua 9y ago
OP 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.