edited by
4,295 views
2 votes
2 votes

If there are n integers to sort, each integer had d digits and each digit is in the set $\{1, 2, \dots, k\}$, radix sort can sort the numbers in

  1. $O(d \: n \: k)$
  2. $O(d n^k)$
  3. $O(d+n)k)$
  4. $O(d(n+k))$
edited by

1 Answer

1 votes
1 votes

http://lcm.csa.iisc.ernet.in/dsa/node210.html

Look at the above link on how algo works.

Lets consider there are 'K' buckets (as given).

Now, for each digit you repeat the following:

1) place the digit of each number in the appropriate bin.  -  ø($n$)

2) append all the 'K' bins sequentially.

Thus, for a single digit, its ø($n + k$),

For 'd' digits, its ø($d(n + k)$)

Answer:

Related questions

3 votes
3 votes
1 answer
2
2 votes
2 votes
2 answers
3