Counting Sort - Learning Module

Loading content...

0/276

Time Complexity: O(n + k)

Understanding the Two-Variable Complexity

Most algorithms we analyze have complexity expressed in terms of a single variable—typically n, the input size. Counting sort breaks this convention: its complexity is O(n + k), where n is the number of elements and k is the range of values.

This two-parameter complexity isn't just a notation quirk—it fundamentally changes how we reason about when counting sort is efficient. The interplay between n and k determines whether counting sort is a linear-time miracle or a catastrophic mistake.

The Central Question

When someone says 'counting sort is O(n)', they're making an implicit assumption: that k = O(n). Without this assumption, the statement is incomplete at best and misleading at worst. Always ask: What is k relative to n?

Phase-by-Phase Complexity Analysis

Let's dissect counting sort's complexity by examining each phase of the algorithm individually. This granular analysis reveals exactly where time is spent.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
function countingSortAnnotated(arr: number[], k: number): number[] {
    const n = arr.length;
    
    // ═══════════════════════════════════════════════════════════
    // PHASE 1: Initialize count array
    // ═══════════════════════════════════════════════════════════
    // Create array of k zeros
    // Time: O(k) - must touch each of k positions
    // Space: O(k) - count array allocation
    const count = new Array(k).fill(0);  // O(k)
    
    // ═══════════════════════════════════════════════════════════
    // PHASE 2: Count occurrences
    // ═══════════════════════════════════════════════════════════
    // Single pass through input array
    // Each increment is O(1) - direct array access
    // Time: O(n) - n elements, O(1) per element
    for (const value of arr) {  // O(n) iterations
        count[value]++;          // O(1) per iteration
    }
    
    // ═══════════════════════════════════════════════════════════
    // PHASE 3: Compute cumulative counts
    // ═══════════════════════════════════════════════════════════
    // Single pass through count array
    // Time: O(k) - k positions, O(1) per position
    for (let i = 1; i < k; i++) {  // O(k) iterations
        count[i] += count[i - 1];   // O(1) per iteration
    }
    
    // ═══════════════════════════════════════════════════════════
    // PHASE 4: Build output array
    // ═══════════════════════════════════════════════════════════
    // Allocate output array: O(n)
    // Single pass through input (backward): O(n)
    // Time: O(n)
    // Space: O(n) - output array allocation
    const output = new Array(n);  // O(n) space
    
    for (let i = n - 1; i >= 0; i--) {  // O(n) iterations
        const value = arr[i];            // O(1)
        count[value]--;                  // O(1)
        output[count[value]] = value;    // O(1)
    }
    
    return output;
}
 
/*
 * TOTAL COMPLEXITY CALCULATION:
 * 
 * Time:
 *   Phase 1: O(k)
 *   Phase 2: O(n)
 *   Phase 3: O(k)
 *   Phase 4: O(n)
 *   ─────────────
 *   Total:   O(k) + O(n) + O(k) + O(n) = O(2n + 2k) = O(n + k)
 * 
 * Space (auxiliary):
 *   Count array: O(k)
 *   Output array: O(n)
 *   ─────────────────
 *   Total:   O(n + k)
 */

Counting Sort Phase Complexity Summary
Phase	Operation	Time	Space
1	Initialize count array (k zeros)	O(k)	O(k)
2	Count occurrences (n elements)	O(n)	—
3	Compute cumulative sum (k values)	O(k)	—
4	Place elements in output (n elements)	O(n)	O(n)
TOTAL	All phases combined	O(n + k)	O(n + k)

The Crucial n vs k Relationship

The O(n + k) complexity behaves very differently depending on how k relates to n. This relationship is the key to understanding when counting sort is appropriate.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
═══════════════════════════════════════════════════════════════════
SCENARIO ANALYSIS: How k affects O(n + k)
═══════════════════════════════════════════════════════════════════
 
Case 1: k = O(1) — Constant range
─────────────────────────────────
Example: Sorting boolean values (k = 2)
         Sorting days of week (k = 7)
 
O(n + k) = O(n + O(1)) = O(n)
 
✅ OPTIMAL: Linear time regardless of n
   Counting sort is definitively superior to comparison sorts.
 
───────────────────────────────────────────────────────────────────
 
Case 2: k = O(n) — Range proportional to input size
────────────────────────────────────────────────────
Example: Sorting n unique values in range [1, n]
         Sorting ages of n people (k ≈ 100, usually << n)
 
O(n + k) = O(n + cn) = O(n)  for constant c
 
✅ GOOD: Still linear time
   Counting sort outperforms O(n log n) comparison sorts.
   This is the "sweet spot" for counting sort.
 
───────────────────────────────────────────────────────────────────
 
Case 3: k = O(n log n) — Range slightly exceeds input size
──────────────────────────────────────────────────────────
Example: Sorting 1000 elements with values up to 10,000
 
O(n + k) = O(n + n log n) = O(n log n)
 
⚠️ NEUTRAL: Equivalent to comparison sorts
   No advantage; comparison sorts may be simpler.
 
───────────────────────────────────────────────────────────────────
 
Case 4: k = O(n²) — Range quadratically larger than input
─────────────────────────────────────────────────────────
Example: Sorting 1000 elements with values up to 1,000,000
 
O(n + k) = O(n + n²) = O(n²)
 
❌ BAD: Worse than comparison sorts
   Merge sort at O(n log n) is strictly better.
   Don't use counting sort here!
 
───────────────────────────────────────────────────────────────────
 
Case 5: k = O(2ⁿ) — Exponential range
─────────────────────────────────────
Example: Sorting n 64-bit integers (k = 2^64)
 
O(n + k) = O(n + 2^64) = O(2^64)
 
❌ CATASTROPHIC: Impractical
   Cannot even allocate the count array.
   Memory required: ~18 exabytes for just the count array!

The Practical Rule

Use counting sort only when k = O(n). In practice, this means k should be at most a small constant multiple of n. If k significantly exceeds n (like k = 10n or more), carefully evaluate whether the overhead is worth it.

Comparison with O(n log n) Sorts

When is O(n + k) actually better than O(n log n)? Let's analyze the crossover points mathematically.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
QUESTION: When is O(n + k) < O(n log n)?
═════════════════════════════════════════
 
Simplifying (ignoring constants):
  n + k < n log n
  k < n log n - n
  k < n(log n - 1)
  k < n log n  (for large n, since log n >> 1)
 
RULE OF THUMB:
  Counting sort wins when k < n log n
  Equivalently: k/n < log n
 
═════════════════════════════════════════
CONCRETE EXAMPLES:
═════════════════════════════════════════
 
n = 1,000 elements
  log₂(n) ≈ 10
  Counting sort wins if k < 10,000
  Example: Sorting 1000 grades (0-100) → k = 101 << 10,000 ✅
 
n = 1,000,000 elements
  log₂(n) ≈ 20
  Counting sort wins if k < 20,000,000
  Example: Sorting ages → k = 150 << 20,000,000 ✅
  Example: Sorting 6-char ASCII strings → k = 128^6 >> 20,000,000 ❌
 
═════════════════════════════════════════
OPERATION COUNT COMPARISON:
═════════════════════════════════════════
 
Sorting n = 10,000 elements with k = 256 (byte values):
 
Counting Sort:
  n + k = 10,000 + 256 = 10,256 operations
 
Merge Sort:
  n log n = 10,000 × 13.3 ≈ 133,000 operations
 
Winner: Counting sort by factor of ~13x
 
───────────────────────────────────────────
 
Sorting n = 10,000 elements with k = 100,000,000:
 
Counting Sort:
  n + k = 10,000 + 100,000,000 = 100,010,000 operations
 
Merge Sort:
  n log n = 10,000 × 13.3 ≈ 133,000 operations
 
Winner: Merge sort by factor of ~750x

Break-Even Points: Counting Sort vs Comparison Sort
Input Size (n)	log₂(n)	Max k for Counting Sort Advantage
100	~7	~700
1,000	~10	~10,000
10,000	~13	~130,000
100,000	~17	~1,700,000
1,000,000	~20	~20,000,000
10,000,000	~23	~230,000,000

Space Complexity Deep Dive

Counting sort's space requirements are often the limiting factor in practice. While time complexity of O(n + k) might be acceptable, the space complexity of O(n + k) can render the algorithm unusable for certain ranges.

Space Components

•Count Array: O(k) — One counter per possible value. For 32-bit integers, this is 4 bytes per counter (assuming int counters), totaling 4k bytes.
•Output Array: O(n) — Holds the sorted result. Same size as input, unavoidable for stable sorting.
•Input Array: O(n) — Already exists (not counted as auxiliary space).
•Miscellaneous: O(1) — Loop variables, pointers, etc.

Memory Requirements for Common Scenarios
Scenario	n	k	Count Array	Output Array	Total Auxiliary
Exam scores (0-100)	10,000	101	~400 bytes	~40 KB	~40 KB
Pixel intensities (0-255)	10M	256	~1 KB	~40 MB	~40 MB
Unicode characters	10,000	~150,000	~600 KB	~40 KB	~640 KB
32-bit integers (full range)	1,000	4.3B	~17 GB	~4 KB	~17 GB ❌
64-bit integers (full range)	1,000	2^64	~74 EB	~8 KB	IMPOSSIBLE

Memory is Often the Bottleneck

Even if O(n + k) time is acceptable, you physically cannot allocate a count array for k = 2^32. This is why radix sort (which uses counting sort on single digits, not the full value) is preferred for large integer types.

Best, Average, and Worst Case Analysis

Unlike comparison-based sorts whose complexity depends on input order, counting sort's complexity depends only on n (input size) and k (value range). The input order doesn't affect performance—all cases are the same!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
═══════════════════════════════════════════════════════════════
COUNTING SORT CASE ANALYSIS
═══════════════════════════════════════════════════════════════
 
BEST CASE:  O(n + k)
─────────────────────
Occurs: Always. Counting sort doesn't have a "better" case.
 
Why: Every phase has fixed work:
  - Must initialize entire count array: O(k)
  - Must count all n elements: O(n)
  - Must compute all cumulative sums: O(k)
  - Must place all n elements: O(n)
 
No early termination possible.
 
═══════════════════════════════════════════════════════════════
 
AVERAGE CASE:  O(n + k)
───────────────────────
Occurs: Always. Input distribution doesn't affect complexity.
 
Why: Same phases, same work. Whether all elements are equal
or uniformly distributed, the algorithm performs identically.
 
═══════════════════════════════════════════════════════════════
 
WORST CASE:  O(n + k)
─────────────────────
Occurs: Always. No adversarial input exists.
 
Why: The algorithm's structure guarantees bounded work.
There's no input that causes extra iterations or comparisons.
 
═══════════════════════════════════════════════════════════════
 
CONTRAST WITH COMPARISON SORTS:
───────────────────────────────
 
Quicksort:
  Best/Average: O(n log n)
  Worst: O(n²) — sorted or reverse-sorted input
 
Insertion Sort:
  Best: O(n) — already sorted
  Average/Worst: O(n²)
 
Counting Sort:
  Best = Average = Worst = O(n + k)
 
This uniformity is a strength: PREDICTABLE PERFORMANCE
regardless of input characteristics.

Predictability Advantage

Counting sort's uniform O(n + k) behavior makes it highly suitable for real-time systems and performance-critical applications where worst-case guarantees matter. You never get surprised by an adversarial input.

Hidden Constants and Cache Considerations

Big-O notation hides constant factors, but in practice, these constants matter significantly. Counting sort has some non-obvious performance characteristics related to memory access patterns.

Cache and Memory Considerations

•Count phase has random access: count[value]++ jumps to wherever value dictates. If k is large and values are random, this causes cache misses. Comparison sorts often have better locality.
•Cumulative sum is sequential: O(k) sequential access is cache-friendly. This phase is fast even for large k.
•Placement phase has dual random access: Reading input and writing to computed positions. Two memory streams = potential cache thrashing.
•Small k = cache-resident counts: If count array fits in L1/L2 cache (~32KB-256KB), counting sort is extremely fast. This means k < ~8000-64000 integers.
•Large k = memory-bound: If count array exceeds cache, every count increment is a cache miss. For k = 1M, expect significant slowdown.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
EMPIRICAL OBSERVATIONS (typical modern hardware):
═══════════════════════════════════════════════════
 
n = 10 million elements
 
k = 256 (bytes):
  Count array: 1 KB (fits in L1 cache)
  Counting sort: ~10ms
  Quicksort: ~300ms
  Speedup: ~30x 🚀
 
k = 10000:
  Count array: 40 KB (fits in L2 cache)
  Counting sort: ~50ms
  Quicksort: ~300ms
  Speedup: ~6x
 
k = 1,000,000:
  Count array: 4 MB (exceeds L3 cache)
  Counting sort: ~500ms (cache miss dominated)
  Quicksort: ~300ms
  Speedup: 0.6x (quicksort wins!)
 
TAKEAWAY:
─────────
The cache-friendliness threshold is around k = 50,000-100,000.
Above this, even if O(n + k) < O(n log n) theoretically,
counting sort may lose in wall-clock time due to cache misses.

Theory vs Practice

Big-O tells you asymptotic behavior, not wall-clock time. For moderate n and large k, a theoretically slower O(n log n) sort with good cache behavior may outperform a theoretically faster O(n + k) counting sort with poor cache behavior.

Amortized Analysis Perspective

When counting sort is used repeatedly with the same k (e.g., as a subroutine in radix sort), the O(k) initialization cost can be amortized across multiple sorts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Radix sort for d-digit numbers with base b (b = k for counting sort)
 * 
 * Each digit requires one counting sort pass.
 * If we naively re-initialize the count array each time: O(dk) overhead
 * With amortization tricks, we can reduce this.
 */
function radixSortOptimized(arr: number[], d: number, b: number): number[] {
    // Reuse count array across all d passes
    const count = new Array(b).fill(0);
    let current = arr.slice();
    let output = new Array(arr.length);
    
    for (let digit = 0; digit < d; digit++) {
        // Clear count array: O(b)
        // But this is amortized over n elements processed
        count.fill(0);
        
        // Extract digit and count: O(n)
        for (const num of current) {
            const digitValue = Math.floor(num / Math.pow(b, digit)) % b;
            count[digitValue]++;
        }
        
        // Cumulative sum: O(b)
        for (let i = 1; i < b; i++) {
            count[i] += count[i - 1];
        }
        
        // Place elements: O(n)
        for (let i = current.length - 1; i >= 0; i--) {
            const num = current[i];
            const digitValue = Math.floor(num / Math.pow(b, digit)) % b;
            count[digitValue]--;
            output[count[digitValue]] = num;
        }
        
        // Swap for next iteration
        [current, output] = [output, current];
    }
    
    return current;
}
 
/*
 * AMORTIZED ANALYSIS:
 * 
 * Total work: d × (O(b) + O(n) + O(b) + O(n)) = O(d(n + b))
 * 
 * For sorting 32-bit integers with b = 256 (1 byte):
 *   d = 4 digits, b = 256
 *   Total: O(4 × (n + 256)) = O(4n + 1024) = O(n)
 * 
 * The O(b) per-pass overhead becomes negligible when n >> b.
 */

Practical Optimization

In radix sort with base 256 (byte-at-a-time), the O(256) clear operation per pass is negligible compared to O(n) counting. For n = 1M elements, 256/1M ≈ 0.03% overhead. Don't over-optimize this.

Comprehensive Complexity Comparison

Let's compare counting sort with the sorting algorithms we've studied, highlighting when each is preferred.

Sorting Algorithm Complexity Comparison
Algorithm	Best	Average	Worst	Space	Stable?	When to Use
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Never (educational only)
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	When swaps are expensive
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Small n, nearly sorted data
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	Guaranteed O(n log n), stability needed
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	General purpose, cache-friendly
Heap Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Guaranteed O(n log n), minimal space
Counting Sort	O(n+k)	O(n+k)	O(n+k)	O(n+k)	Yes	Integer keys, k = O(n)

The Trade-off Spectrum

Counting sort trades generality for speed. It can't sort arbitrary objects, but for bounded integers, it's unbeatable. Always consider the full picture: input characteristics, stability requirements, memory constraints, and value ranges.

Complexity Analysis in Interview Context

In technical interviews, stating 'O(n + k)' correctly and explaining the implications demonstrates sophisticated understanding. Here's how to discuss counting sort complexity professionally.

Best Practices for Complexity Discussion

•Always state both parameters: Say 'O(n + k)' not 'O(n)'. Then clarify what k is for the specific problem.
•Justify k = O(n): If claiming linear time, explain why k is bounded. 'Since we're sorting ages, k ≤ 150, so O(n + k) = O(n).'
•Compare with baseline: 'Counting sort gives us O(n) versus O(n log n) for comparison sorts, a significant improvement for this use case.'
•Acknowledge trade-offs: 'We're using O(k) extra space for the count array. With k = 10000, that's ~40KB, which is acceptable.'
•Know when it fails: 'If values were arbitrary 64-bit integers, counting sort wouldn't work—we'd use radix sort instead.'

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
INTERVIEWER: "Sort an array of n integers where each value is 
              between 0 and 10000. What's your approach?"
 
OPTIMAL RESPONSE:
────────────────
"I'll use counting sort since we have a bounded integer range.
 
Time Complexity: O(n + k) where k = 10001.
Since k is a constant (doesn't grow with n), this simplifies 
to O(n + 10001) = O(n) — linear time.
 
Space Complexity: O(n + k) = O(n + 10001) = O(n).
The count array is ~40KB (10001 × 4 bytes), negligible for 
modern systems.
 
This beats comparison-based sorts which are Ω(n log n).
 
For n = 1 million elements:
  Counting sort: ~1M operations
  Merge sort: ~20M operations
  ~20x improvement.
 
The algorithm is also stable, which would matter if these 
integers were keys for objects with associated data."

Summary: Mastering O(n + k) Analysis

Understanding counting sort's O(n + k) complexity requires analyzing both parameters and their relationship. This nuanced understanding separates surface-level knowledge from true mastery.

Key Takeaways

•Complexity is O(n + k), not O(n): Both parameters matter. Never simplify without justification.
•k must be O(n) for linear time: If k >> n, counting sort loses its advantage over O(n log n) sorts.
•Space is also O(n + k): Large k makes counting sort impractical even if time complexity is acceptable.
•All cases are identical: Best = Average = Worst = O(n + k). No adversarial inputs exist.
•Cache effects matter in practice: Large k causes cache misses that can negate theoretical advantages.
•Compare crossover points: Counting sort beats comparison sorts when k < n log n approximately.

Page Complete

You now have a comprehensive understanding of counting sort's O(n + k) complexity: how it decomposes across phases, how n and k interact, and when the algorithm provides genuine speedup over alternatives. Next, we'll synthesize everything into practical guidance on when counting sort is the right choice.