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.


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

  • $\begingroup$ So essentially, the expansion of the number into base-n is what causes it to not be a linear-time algorithm? $\endgroup$
    – cdknight
    Commented Apr 26 at 14:45
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Apr 27 at 15:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.