The Gateway to Computer Science Excellence

+2 votes

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

- O(d n k)
- O(d n$^k$)
- O(d+n)k)
- O(d(n+k))

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

52,218 questions

59,890 answers

201,084 comments

118,128 users