0 votes 0 votes 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 Algorithms sorting time-complexity + – Smishra95 asked Sep 28, 2018 • edited Jun 18, 2022 by makhdoom ghaya Smishra95 2.1k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Shaik Masthan commented Sep 28, 2018 reply Follow Share Radix sort, have depends upon no.of digits ===> O(n.k) k means no.of digits to represent the n6 value ===> it is not linear time. But counting sort is takes O(n) time only. 1 votes 1 votes Magma commented Sep 28, 2018 reply Follow Share Shaik Masthan if range is (1 to n6) then time complexity of counting sort : O(no of keys in the input array + range ) O(n+n6) 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 1 votes 1 votes Shaik Masthan commented Sep 28, 2018 reply Follow Share @Magma yes, you are right ! Thanks for correcting me 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes 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) Gurdeep Saini answered Jan 14, 2019 Gurdeep Saini comment Share Follow See all 0 reply Please log in or register to add a comment.