Re:Bead sort: faster than O(N log N) sort
by tybris on Monday June 22, 2009 @08:53AM
(#668657)
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).
[ Parent
| on HN ]
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.