3 ms·
In reasonable key representations, k would be constant and hence ignored in algorithmic analysis. In 32 bit integers, for example, 0 takes just as many bits as
by bartonfink 15y ago
In reasonable key representations, k would be constant and hence ignored in algorithmic analysis. In 32 bit integers, for example, 0 takes just as many bits as 2^32 - 1 and you have to compare them all each time.
- jacobolus 15y agoSince you sort by digit, if you're going to make your radix be the size of an integer, you'll to construct that many empty lists; in actual practical implementations of radix sort, the radix is some relatively small number, and so you end up with O(nk). I guess if you want you can say that k is actually O(log(maxint)), if all of your integers are < maxint. But that ends up being quite a sizable constant term if you really want to consider it constant. If you're going to do algorithmic analysis that entirely ignores large constants, it's a bit strange to simultaneously declare that all your integers will be bounded by some particular cutoff.