0 votes 0 votes As we know the time complexity of solving the greedy knapsack algorithm depends mainly on the sorting algorithm used, Can we use counting sort as the sorting algorithm to reduce the time complexity to O(n)? Algorithms algorithms self-doubt sorting time-complexity + – tusharb asked Feb 18, 2022 tusharb 728 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments tusharb commented Feb 18, 2022 reply Follow Share @raja Why? Any source to read why we can’t do that? 0 votes 0 votes tusharb commented Feb 18, 2022 reply Follow Share @kabir I think another case can be that counting sort deals with integers, but knapsack can deal with floating points, will this logic be true? 0 votes 0 votes Kabir5454 commented Feb 18, 2022 reply Follow Share Yes you can say that but then someone can argue that we can use radix sort which can sort floating point numbers in linear time given we fulfill all the assumption of radix sort. https://stackoverflow.com/questions/5149410/radix-sort-in-c-on-floating-points-numbers So, it better to say that we don't want to assume anything about the input and use comparison based and use any type of number floating or integer in O(n) . 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes @tusharhigh Counting sort is most efficient if the range of input values is not greater than the number of values to be sorted… In that scenario, the complexity of counting sort is much closer to O(n), making it a linear sorting algorithm.... 1. https://en.wikipedia.org/wiki/Counting_sort#Complexity_analysis 22 answered Feb 18, 2022 22 comment Share Follow See all 0 reply Please log in or register to add a comment.