1.1k views

If there are n integers to sort, each integer had d digits and each digit is in the set {1, 2, ...., 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))

recategorized | 1.1k views
0

+1 vote

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)$)

by Boss
0
It should be n*k for a single digit as single digit is compared with k bins for placement. and for d digits it should be total n*k*d i dont understand why n+k is there??