Time ComplexityLesson 49Free preview

Counting Sort

This lesson is part of DSA · All levels

Summary

Counting sort has a complexity of O(n + k) with n number of elements and k range of values. He makes a k-sized array of numbers and then composes the results of the accumulation of the numbers. The advantage is linear and stable, but becomes inefficient when k is much larger than n because memory and counting time arrays are swelling.

Key points

Complexity of time
Arrays of counts require memory
Stable and non-comparative
It's not efficient when the range of k values is much larger than n.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.