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

What is the time complexity of counting sort?

---

O(n)

---

Bro I think you should check counting sort once.

Counting sort - Wikipedia

---

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

---

@raja It is linear time, I guess we can assume it to be O(n) instead of O(n+k)

---

 I guess we can assume it to be O(n) instead of O(n+k)

We can’t. 

---

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.

---

@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