Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant

Question

So i came upon this question where:

we have to sort $n$ numbers between $0$ and $n^3$ and the answer of time complexity is $\mathcal{O}(n)$ and the author solved it this way:

first we convert the base of these numbers to $n$ in $\mathcal{O}(n)$, therefore now we have numbers with maximum 3 digits.

now we use radix sort and therefore the time is $\mathcal{O}(n)$

so i have three questions :

1. is this correct? and the best time possible?

2. how is it possible to convert the base of n numbers in $\mathcal{O}(n)$? like $\mathcal{O}(1)$ for each number? because some previous topics in this website said its $\mathcal{O}(M(n) \log(n))$?

3. and if this is true, then it means we can sort any $n$ numbers from $0$ to $n^m$ in $\mathcal{O}(n)$?

Answer 1

The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \% \ b$

where $\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.

---

$^*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.