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

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.

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.

• So essentially, the expansion of the number into base-n is what causes it to not be a linear-time algorithm? Commented Apr 26 at 14:45
• Yes, consider how two numbers are multiplied and divided in long division and try to scale it up by $10^x$, then compare FLOPS in state of the art hardware. Commented Apr 27 at 15:23