sorting

Question

Given an array where numbers are in range from 1 to n6 , which sorting algorithm can be
used to sort these number in linear time?
A. Not possible to sort in linear time
B: Counting Sort
C: Radix Sort
D. Quick Sort

Comments

Radix sort, have depends upon no.of digits ===> O(n.k) 

k means no.of digits to represent the n⁶ value ===> it is not linear time.

But counting sort is takes O(n) time only.

---

Shaik Masthan 

if range is (1 to n⁶)

then time complexity of counting sort : O(no of keys in the input array + range )

                                                                            O(n+n⁶)

                                                                 therefore, it's not linear

but if do with radix sort

time complexity will be :  O(n log n) which also not  linear

therefore , A )  Not possible to sort in linear time 

 

 

 

---

@Magma

yes, you are right ! 

Thanks for correcting me

Answer 1

Radix sort is correct answer

radix sort complexity =O(d(n+b))

now maximum no is $n^{6}$

so lets take base n  so digit in maximum no is $log_{n}(n^{6}-1) =6$

and base=n

so the complexity is O(6(n+n))=O(2n)=O(n)