Hacker News Reader

Comment by jaydub | Hacker News Reader

http://en.wikipedia.org/wiki/Radix_sort

Radix-sort is actually not linear. The algorithm will only work if the word-length w>=log(n) (because otherwise you can't store all possible n) so O(nw) is practically the same thing as O(nlog(n))

Not sure what you mean by storing all possible n. Radix sort is O(nw) and for most use-cases w is smaller than log(n).

A word which is w bits long can hold a number between 0 and 2^w-1. If you want to hold a larger interval than that you need to increase the size of w.

Perhaps you can make it smaller than log(n) for many use cases by restricting the type of input you accept but O(f(x)) only refers to the worse case.

That's certainly true in general, but by choosing a fixed-length word size (i.e. 16, 32 or 64 bit integers) you can preselect w so that runtime is predictably O(n). I can't see a way of doing that with most other O(n log(n)) sorting algorithms. Additionally, the constant factor is typically low compared to other algorithms.

Restricting the size of w (and therefore also n) does not make it linear.

Lets say you have restricted w to 32. Then you also know that n <= 2^32. If you now for instance are using mergesort then you also know that the number of recursions are at most 32 (since you split the input in half each time), i.e. it executes within at most 32n operations. So with that logic mergesort would also be linear.

No, in the merge sort example it's not 32n operations, but a maximum of 32 levels of splits, but the number of comparisons, which dominate runtime, is still k * n * log(n). Not so for radix sort, because there are no direct comparisons. By choosing a word length in advance (often hard-coded) the number of items to sort affects the runtime linearly.

I think you are mixing runtime scalability with the actual complexity. Big-O definition from Wikipedia: Let f(x) and g(x) be two functions defined on some subset of the real numbers. One writes f(x) = O(g(x)) as x -> infinity if and only if, for sufficiently large values of x, f(x) is at most a constant times g(x) in absolute value. That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that |f(x)| <= M|g(x)| for all x > x0.

In the above case M = 32, f = mergesort and g(x) = x because no matter of large input you have mergesort will always take less than or equal to 32n operations (since log(n)<=32) .

Reply on news.ycombinator.com