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...