4 ms·
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).
by tybris 17y ago
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).
- Yrlec 17y agoA 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.