edited by
20,578 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

2 votes
2 votes

Radix sort sorts numbers from LSB to MSB one column of digits at a time.

Each sort of a column (imagine a Matrix where each row is a candidate number) takes $O(n)$ time

Hence total time complexity would be $O(pn)$ where p = number of columns or the word length.

 

The maximum number we'd require to sort would be $n^k$. (given)
The word length of such a number would be $log (n^k)$ or $klogn$ or $O(logn)$ because k is independent of n.

Hence p = $O(logn)$

So, time complexity of radix sort here would be $O(pn) = O(nlogn)$

 

Option C

2 votes
2 votes
$Answer: option B$

Method 1: n elements range of elements n^(k/2) to n^k

No. of digits (d) = logbase10(n^k) = θ(klogn)
Radix sort time complexity : θ(n * k * logn)

$Method 2$ : n elements given

Convert each element into radix n number system. Time complexity for this n elements θ(n)

Number of digits is become log basen(n^k) = k digits.

Applying radix sort time complexity θ(n * k)
0 votes
0 votes
Time complexity of Radix sort=O(WN)

W=log(n^k)=klogn

So Tc=O(nlogn) Here
Answer:

Related questions

15 votes
15 votes
4 answers
2
Ishrat Jahan asked Oct 29, 2014
9,156 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$...