Why is it impossible to do a linear time radix sort on n integers and ranging from $0$ to $n^{3} - 1$?

Question

I propose by doing a base-n expansion of the numbers, we have that since there are $n^{3}$ values and $n$ digits in this expansion, there are a total of $\log_{n} n^{3} = 3$ digits. Note in this base-n expansion there are $n$ possible values of digits. Therefore $d = 3$, and $k = n$.

$$ O(d(n+k) = O(3(n + n)) = O(6n) = O(n) $$

So it is possible to do a linear time radix sort with these constraints.

I am told this is impossible because it is nonsensical to consider a base-n expansion of the numbers when doing radix sort because n is an arbitrarily large value.

What is wrong with my reasoning? I realize there are duplicate questions on this (namely Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant), but I want to understand the reasoning why this is not possible in the previous paragraph.

Answer 1

When you consider an algorithm you are given certain assumptions, in this case $n$ is implied to be in base 10 so you would have to compute the base $n$ expansion in addition to the radix sort. You change basis by computing

$$ n = n_a = n_{a,0}\cdot a^0 + n_{a,1}\cdot a^1 + n_{a,2}\cdot a^2\ldots $$

and to find out each of the coefficients you can divide it by the exponent

$$ \begin{split} n_{a,0}:& \frac{n}{a^0} = n_{a,0} + n_{a,1}\cdot a^1 + n_{a,2}\cdot a^2\ldots \implies \frac{n}{a^0} \mod a = n_{a,0} \\ n_{a,1}:& \frac{n}{a^1} = n_{a,0}\cdot a^-1 + n_{a,1} + n_{a,2}\cdot a^2\ldots \implies \frac{n}{a^1} \mod a = n_{a,1} \\ n_{a,2}:& \frac{n}{a^2} = n_{a,0}\cdot a^-2 + n_{a,1}\cdot a^-1 + n_{a,2}\ldots \implies \frac{n}{a^2} \mod a = n_{a,2} \end{split}. $$

Now set $n=n^3-1$ and $a=n$, then the second digit is

$$ \frac{n^3-1}{n^1} \mod n \equiv \frac{n^3-1}{n} \mod n $$

In this case there are only 3 digits that need to be calculated but since $n$ can be arbitrarily large it would be computationally unfeasible to compute the exponents followed by a division with another large number.