137 views
0 votes
0 votes

If Radix sort is used to sort an array of n integers which are in the range (n^{log_{2}d}, n^{d^{2}}),

where d is some function of input size, the time taken would be?

(A) O(nd^{2})

(B)O(n^{2}dlogn+n^{2}\ log_{2}d\ log_{2}n)

(C) O(n^{2}d^{2}+n^{2}\ log_{2}n)

(D) O(nd^{2}log_{2}n)

I know that Radix sort takes $\theta(d(n+k))$ times over 'd' digits of numbers, and the counting sort it uses takes $\theta(n+k)$ times in each pass where k represents the range of input numbers.

I am unable to solve this.

Please help.

 

Please log in or register to answer this question.

No related questions found