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

  1. O(d n k)
  2. O(d n$^k$)
  3. O(d+n)k)
  4. O(d(n+k))
in Algorithms by Veteran
recategorized by | 1.1k views

1 Answer

+1 vote

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
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??

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
118,128 users