Time complexity of expanding decimal to new base

Question

There is already a post on this topic on stackoverflow.

Nevertheless, I am asking the question here again, primarily because I do not understand the answer given there, and also because I have some takes on the problem I would like to supplement with.

To reiterate, we have a problem in CLRS which goes like this:

Show how to sort $n$ integers in the range $0$ to $n^3-1$ in $O(n)$ time.

There seems to be a consensus that we first convert the numbers into base $n$, which ensures that each number is made up of at most 3 digits. Then we can use radix sort to sort the number in $\Theta(3(n+n)) = \Theta(n)$ (the parameter $k$ equals $n$ because we are in base $n$).

What I am concerned with is the cost of converting the $n$ numbers to and from base $n$. Converting back to decimals is $\Theta(1)$ obviously, so $n$ conversions equals $\Theta(n)$. But converting a decimal to another base takes $\Theta(\log n)$, so that the first $n$ conversions to base $n$ would take $\Theta(n\log n)$ time, and break the time complexity of $\Theta(n)$ of the algorithm overall.

I have read that you can view the expansion as a $O(1)$ operation under the RAM model though I do not understand why (probably because I do not understand the difference between the RAM and BIT models in connection to complexities). In the original post the answer given also tries to explain how if integer arithmetic is done in $O(1)$ time, then "... converting a number to base $n$ is basically most significant digit: x/n, least significant digit: x%n," which I really don't get any of.

Answer 1

Let me start with a short introduction on computation models. A (C-like) computation model specifies the inventory of operations, and the cost of each operation. Two popular computation models are the bit complexity model and the word RAM model, though the latter doesn't really have a canonical description.

In the bit complexity model, all basic operations operate on bits (except for instructions like JUMP, which we ignore here for simplicity), and they all have constant cost. The exact cost of each operation, and the exact repertoire of operations, isn't important (as long as we have a complete set of operations!), since it only affects the running time by a constant factor.

In the word RAM, we associate with each input a parameter $n$ which is a "yardstick" for the input. For example, a function that accepts an array of length $n$ will use the input length as a parameter (but this only works if the array entries are "small" – more on that later). In the word RAM, all basic operations operate on machine words. What is a machine word? It is a value which is $C\log n$ bits long, for some constant $C$ depending on the algorithm (we will see that $C$ doesn't really matter shortly). Each operation on machine words takes time $O(1)$. The operations allowed are arithmetic operations (addition, subtraction, multiplication, division with remainder), comparisons, bitwise operations (NOT, AND, OR, XOR), and shifts. Since we can simulate an operation on words of width $C\log n$ bits using $O(1)$ operations on words of width $\log n$ bits (where the constant depends on $C$), the value of $C$ doesn't really matter.

Let us now come back to the definition of $n$. We usually assume that the input consists of $Cn$ machine words of length $\log n$ bits (for some constant $C$ depending on the algorithm), for a total input length of $Cn\log n$ bits. We obtain an equivalent definition by setting $n$ to be the input length in bits, essentially since $\log(Cn\log n) = \Theta(\log n)$.

(We have not touched on the random access aspect of the RAM model, and on the uniformity aspect of both models, since these are not relevant here.)

---

Now back to your question. Since your array consists of numbers of length $3\log n$ bits (so we are using $n$ as our yardstick for the word RAM model), we can assume that each of them fits into a single machine word. Packing and unpacking these numbers to base $n$ is very easy:

UNPACK($m$):

1. $m_0 = m \bmod n$.
2. $m_1 = \lfloor m/n \rfloor \bmod n$.
3. $m_2 = \lfloor m/n^2 \rfloor$.
4. return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

1. return $n^2 m_2 + n m_1 + m_0$.

You can see that both operations use $O(1)$ operations, so take $O(1)$ time in the word RAM model. With some care, the implementation can be improved to use $O(d)$ operations for numbers up to $n^d$:

UNPACK($m$):

1. $m_0 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
2. $m_1 = m \bmod{n}$, $m = \lfloor m/n \rfloor$.
3. $m_2 = m \bmod{n}$.
4. return $m_2,m_1,m_0$.

PACK($m_2,m_1,m_0$):

1. return $m_0 + n(m_1 + n (m_2))$.

Answer 2

You pick the right base. If you have numbers in binary representation, and all the numbers are less than $2^{3k}$, then you choose base $2^k$. If you have numbers in decimal representation, and all the numbers are less than $10^{3k}$, then you choose base $10^k$. In both cases, the conversion is trivial.

Now if your n numbers are up to $n^3$, and take up to $3 \log n$ bits, then just the task of moving each item into its right place has to move at least $3n \log n$ bits if no item is in the right place. That factor $\log n$ is usually ignored - in practice, modern processors can move 256 bits in a single instruction, and $n = 2^{85}$ means you are not going to sort that array in your lifetime, so the exact time needed is irrelevant.