edited by
4,276 views

1 Answer

Best answer
4 votes
4 votes
Radix Sort takes $O(d*(n+b))$ time where $b$ is the base, $d$ is the numbers of digits present in the highest integer in the given range, and $n$ is the numbers of integers to be sorted.

Here, the maximum integer is $n^5-1$. So $d$, the number of digits is $O(log \; (n^5-1)) = O(log \; n)$. Value of $b$ is 10.

So overall time complexity is $O(log \; n * (n+10)) = O(n\; log\;n)$
selected by

Related questions

1 votes
1 votes
2 answers
2
Pradeep Verma asked Jul 7, 2018
501 views
3 votes
3 votes
3 answers
3
sunil sarode asked Jan 23, 2018
2,915 views
I am not able to get this formula (number of input * number of digit *base of number )I am not getting how base of number is important ?Thanks :)
3 votes
3 votes
1 answer
4
hem chandra joshi asked Nov 25, 2017
302 views
From CLRS the complexity of radix sort is theta(d(n+k)) where d is # of digits , k is range and n is numbers . So how option C is right . Plz solve it on the basis of min...