3 ms·

If you use radix sort the sorted array approach becomes O(N). And since the actual order is irrelevant, radix sort will work for any fixed size data structure (

If you use radix sort the sorted array approach becomes O(N). And since the actual order is irrelevant, radix sort will work for any fixed size data structure (or even objects of varying size if you just sort and split the array according to size first). And if you're worried that for objects of size k, radix sort runs in O(n k), rather than O(n), I'd like to point out that n*k = N is simply the size in memory, so it is in fact still linear in the size of the input, so it truly is O(N). For string-like objects using a radix tree might be better, although the result is pretty similar.

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 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 ago
    It 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 ago
      It'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 ago
      For 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.

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 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 ago
  It 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 ago
    It'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 ago
    For 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.