Time complexity in radix sort is depends on the number of digits present in the maximum number ( largest number cuz if 500 is the largest number therefore 1 is also represent as 001)
and whatever is the number of digits present in the maximum number we're going to do it those many times
and for every digits we're repeat the sorting those many times
Now since, the range here is known : means we take integer therefore base is between (0 to 9) , therefore best thing is you go with a counting sort .
And we know that time complexity of counting sort : O(n+b)
where , n is the size of the array
b is the base
so,
let number of digits present in the maximum array = d
time complexity of radix sort : No of digits in the Maximum number * apply counting sorts
= d * O(n+b)
here, largest number is given : nd^2
relationship between base and number of digits = floor(logbn) +1
therefore number of digits : log10 (nd^2) +1 = d2 log n +1
= (d2 log n +1) * O(n+10)
= O(n*d2 log n)