GB DSA-Test 4-Question 17

Question

If Radix sort is used to sort an array of n integers which are in the range ,

where d is some function of input size, the time taken would be?

(A) 

(B)

(C) 

(D) 

Comments

what's the answer given ??

I got  D...I'm not sure though

---

Yes Answer is d. please explain how?

---

check the answer...if you have any doubts ask me

Answer 1

Time complexity in radix sort is depends on the number of digits present in the maximum number ( largest number cuz  if 500 is the largest number therefore 1 is also represent as 001)

 

and whatever is the number of digits present in the maximum number we're going to do it those many times

and for every digits  we're  repeat the sorting those many times 

Now since, the range here is known : means we take integer therefore base is between (0 to  9)  , therefore best thing is you go with a counting sort .

And we know that time complexity of counting sort : O(n+b)

where , n is the size of the array

             b  is the base

so,

 let number of digits present in the  maximum array = d

time complexity of radix sort :  No of digits in the Maximum number * apply counting sorts

                                                      = d * O(n+b)

            here, largest number is given :  nd^2

      relationship between  base and number of digits = floor(logbn) +1

     therefore number of digits  :  log10 (nd^2) +1 =  d2 log n +1

                                                            =  (d2 log n +1) * O(n+10)

                                                            = O(n*d2 log n)

Comments

@Shaik Masthan-Refer Coremen once.There they have explained it how using counting sort.

---

if it is calculated base of n, then A) will be ans.

but base of log is 2

---

@Shaik Masthan sir why not the optimal ans is taken, that is option (a) ,by taking base as n?