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 714 views answer comment Share Follow See all 10 Comments See all 10 10 Comments reply raja11sep commented Feb 18, 2022 reply Follow Share What is the time complexity of counting sort? 0 votes 0 votes tusharb commented Feb 18, 2022 reply Follow Share O(n) 0 votes 0 votes raja11sep commented Feb 18, 2022 reply Follow Share Bro I think you should check counting sort once. Counting sort - Wikipedia 0 votes 0 votes Kabir5454 commented Feb 18, 2022 reply Follow Share I dont think applying counting sort reduce it to O(n) as counting sort has his own limitation.This problem given in cormen in exercise to think we can do this at O(n) time or not.And we have an implementation for it in O(n) time as well. see here the algorithm for your reference :-https://cs.stackexchange.com/questions/11620/fractional-knapsack-in-linear-time 1 votes 1 votes tusharb commented Feb 18, 2022 reply Follow Share @raja It is linear time, I guess we can assume it to be O(n) instead of O(n+k) 0 votes 0 votes raja11sep commented Feb 18, 2022 reply Follow Share I guess we can assume it to be O(n) instead of O(n+k) We can’t. 0 votes 0 votes Kabir5454 commented Feb 18, 2022 reply Follow Share The time complexity of counting sort is O(n+k). where k is the range of input . But it is only possible if we know the value of k beforehand. so if we implement counting sort we can assume that we know the range of input beforehand and implement it to sort at O(n+k). for any problem where sorting takes O(nlogn) time we can’t simply assume that we have counting sort which can run O(n+k) so our sorting will be in O(n) time and problem time complexity reduce to O(n) that is not the case as we don’t know the range of input k beforehand in inputs. 1 votes 1 votes 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.