edited by
20,516 views
66 votes
66 votes

If we use Radix Sort to sort $n$ integers in the range $\left (n^{k/2}, n^k \right ]$, for some $k > 0$ which is independent of $n$, the time taken would be?

  1. $\Theta(n)$
  2. $\Theta(kn)$
  3. $\Theta(n \log n)$
  4. $\Theta(n^2)$
edited by

7 Answers

Best answer
63 votes
63 votes

Answer: C

The complexity of Radix Sort is $O(wn)$, for $n$ keys which are integers of word size $w$.

Here, $w = \log_2(n^k) = k \times \log_2(n)$

So, the complexity is $O(wn) = O(k \times \log_2(n) \times n)$, which leads to option C.

edited by
56 votes
56 votes

TIME COMPLEXITY OF RADIX SORT IS THETA ((n+k)d))

where n= no of numbers

k= base of number system

d= no of digits.

Here let base is b. 

Numbers are are in range (n^k/2,n^k).

No of digits required= (log n^k)base b=k log n base b.

thus time complexity =( n+b) k log n base b.

Since b and k are constants with respect to n  time complexity = Θ(nlogn)

10 votes
10 votes

I am not sure my approach is correct or not but I have seen something like this in CLRS.

When we represent nk/2 and nk in base n, we need atmost k+1 bits.

And to sort k+1 bit positions apply any stable sorting algorithm like counting sort(O(n) time ).

So, time complexity = O(k*n) i.e. apply counting sort for each of the k+1 bit positions.

So, answer (b).

If my approach is wrong,can anyone explain why ??

5 votes
5 votes

Answer would be C.

P.S- The question mention "n integer values" somehow implies it is decimal representation system. So we can say k=10 and d=k*$log_{10}N$

Time complexity = O (n.log n)

edited by
Answer:

Related questions

15 votes
15 votes
4 answers
2
Ishrat Jahan asked Oct 29, 2014
9,150 views
Consider the code fragment written in C below :void f (int n) { if (n <=1) { printf ("%d", n); } else { f (n/2); printf ("%d", n%2); } }What does f(173) print?$010110101$...