Question

Suppose we radix sort n words of b bits each. Each could be viewed as having (b/r) digits or r bits each. for some integer r

now fill in the blanks

a)Each part of radix sort takes _________ time

2) At min r= _______

3)T(n,b)= ____________

Answer 1

a. Each digit can have 2^r values. So each part of radix sort will take time O(n+2^r). 

b. In general the time complexity will be O((b/r)(n+2^r)). To minimize this complexity r should be equal to b. If r=b , then complexity will be equal to O(n+2^b) = O(n) which is optimal. (This answer is by assuming you want the value of r at optimal or minimal runtime).

c. If r>= logn then T(n,b) = O(bn/logn), else T(n,b) = O(n).  This holds for all b>= n.

Please refer text in TH Cormen book after 8.4 Lemma.