There is already a post on this topic at

https://stackoverflow.com/questions/32677054/time-complexity-of-number-base-conversion

Nonetheless i ask the question here again, primarily because i do not understand the answer giver there and for another 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)) (k=n because we are in base n) =theta(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(nlog(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 model 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, lease significant digit: x%n," which i really dont get any of.

I hope someone can help my stupid brain understand.