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.