That is incorrect. k has no relation to n. k is the size of the range of possible values in the input and n is the actual number of elements in the input. To i

That is incorrect. k has no relation to n. k is the size of the range of possible values in the input and n is the actual number of elements in the input. To illustrate, consider sorting 32 bit integers. If the radix is one bit (i.e. radix=1 bit and k=2 * 32 [32 "digits" and 2 possible values for each "digit"]) then radix sort is O(64n) = O(n). Now consider, cutting up the 32-bit int into byte size chunks (i.e. radix=8 bits and k=4 * 256 [4 "digits" and 256 possible values for each "digit"]). In which that case radix sort is O(1024n). Note that we are able to determine the value of k without any idea of what n may be. In practice even for small n (n>200), a straight forward implementation of radix sort is faster than any O(nlogn) sort.