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).
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.