Algorithm self doubt

Question

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)?

Comments

@raja Why? Any source to read why we can’t do that?

---

@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?

---

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) .

 

Answer 1

@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