CODEWITHSUNDEEP
algorithmsortingcounting
user8858222
user8858222

Reputation:

Can we make the counting sort algorithm for n element with O(n) space complexity?

I had a midterm exam today and one the of algorithm problem was the "Can we make the space complexity for counting sort O(n) for n elements". Actually I couldn't find any solution for these. Is there any one know any algorithm or data structure. I want to learn the answer and think about it. Thanks a lot.

Upvotes: 1

Views: 159

Answers (1)

Yola
Yola

Reputation: 19043

If we use an array for counting in counting sort then it requires space equal to the difference between the maximum and minimum key values. We can use hash-table, then we can reduce space complexity to linear relative to the number of elements in the input. But in this case, hidden constant might be too big and performance might deteriorate.

Upvotes: 3

Related Questions