Course contentsShow
← Computer Science
Lesson 791 of 2,87218. Sorting AlgorithmsFree lesson

Counting Sort: Space-Time Tradeoffs

Analyzing when counting sort is practical based on the range k of input values versus n.

Counting Sort: Space-Time Tradeoffs

You'll learn when counting sort is practical by comparing the range of input values to the number of elements.

The Core Tradeoff

Counting sort achieves O(n + k) time complexity, where n is the number of elements and k is the range of input values (from minimum to maximum). This breaks the O(n log n) comparison-sort barrier, but there's a catch: it also requires O(k) extra space for the counting array.

The big question: when does this tradeoff make sense?

When Counting Sort Shines

Counting sort is practical when k is small relative to n—ideally when k = O(n).

Example: Sorting 1,000,000 exam scores (ranging 0-100):

  • n = 1,000,000
  • k = 101
  • Time: O(1,000,000 + 101) ≈ O(n) — blazingly fast!
  • Space: O(101) — negligible

When Counting Sort Fails

If k >> n (k much larger than n), the algorithm becomes impractical.

Example: Sorting 100 arbitrary 32-bit integers:

  • n = 100
  • k = 4,294,967,296 (range of 32-bit values)
  • Time: O(100 + 4 billion) ≈ O(k) — terrible!
  • Space: O(4 billion integers) — millions of bytes wasted

Analogy: It's like reserving a hotel room for every possible guest ID number (0 to 4 billion) when you only expect 100 guests. The infrastructure cost overwhelms the benefit.

Practical Rule of Thumb

Use counting sort when:

  • You know k in advance
  • k ≤ 10n (rough guideline)
  • Space for k integers is available

Otherwise, stick with O(n log n) comparison sorts like quicksort or mergesort.

Key Takeaway: Counting sort trades space for speed—it's incredibly fast when the value range k is small compared to the dataset size n, but becomes impractical when k dominates.