I am reading introduction to algorithms 2nd edition, and there is a question says that we can sort n integers, who are between 0 and n3-1 in linear time. I am thinking of IBM's radix sort approach. I start with the least significant digit, separate numbers with respect to least significant digit, and then sort, then separate with respect to next least significant digit and so on. Each separation takes O(n) time. But i have a doubt, for example, if one of the number consists of n digits, then the algorithm takes O(1*n+2*n+...+n*n)=O(n2) time, right? Can we assure that numbers consist of fewer than n digits, or can anybody give another hint for the question? Thanks
Radix Sort complexity is O(dn) with d as the number of digits in a number.
The algorithm runs in linear time only when d is constant! In your case d = 3log(n) and your algorithm will run in O(nlog(n)).
I'm honestly not sure how to solve this problem in linear time. Is there any other piece of information regarding the nature of the numbers I'm wondering if there is any other piece of information missing about the nature of numbers...