Common Complexity Classes in Practice: Searching & Sorting

Algorithms & Complexity

Chapter 7 · Common Complexity Classes in Practice: Searching & Sorting

Binary search and sorting have been referenced throughout this course — Chapter 1's opening comparison, Chapter 3's loop gotchas, Chapter 5's recurrence setup, Chapter 6's Master Theorem proof. This chapter finally gives them their own full treatment, with real measured numbers instead of just formulas.

Binary Search — A Real Trace

Searching a sorted 15-element array (values 1–15) for the target 12:

Step	lo	hi	mid index	value at mid	Decision
1	0	14	7	8	8 < 12 → search right half
2	8	14	11	12	Found

Just 2 comparisons to find one element among 15 — each step throws away half the remaining candidates, exactly Θ(log n), formally confirmed by the Master Theorem in Chapter 6.

The precondition that makes it all work

Binary search only works on already-sorted data — the halving logic depends entirely on knowing which half a target could be in. Sorting first costs something upfront (this chapter's own second half), but pays for itself the moment more than one search is needed against the same data.

Sorting: O(n²) vs. O(n log n), Measured Directly

Bubble sort compares adjacent elements repeatedly — simple, but Chapter 3's own nested-loop pattern, giving O(n²). Merge sort (Chapters 5–6) is O(n log n). Rather than trust the formulas alone, here are actual comparison counts on random data:

n	Bubble sort comparisons	Merge sort comparisons	Ratio
10	45	24	1.9×
100	4,950	534	9.3×
1,000	499,500	8,708	57.4×

The gap doesn't just grow — it grows faster than n itself

Going from n=10 to n=1,000 (a 100× increase in input), the gap between the two algorithms widened from under 2× to over 57×. This is exactly what Chapter 2's own growth-rate table predicted in the abstract — now confirmed with real comparison counts on real data, not just formulas.

Quicksort: An Honest Average-vs-Worst-Case Gap

Quicksort is, in typical practice, one of the fastest sorting algorithms available — O(n log n) average case. But Chapter 4's own best/worst/average distinction applies directly here:

Quicksort's worst case is genuinely O(n²)

If the "pivot" element quicksort partitions around is consistently a poor choice — the smallest or largest remaining value, over and over — the algorithm degrades to O(n²), the exact same class as bubble sort. This happens, notably, on already-sorted or specifically-crafted adversarial input if the pivot selection is naive. Real implementations guard against this with randomized or median-of-three pivot selection specifically to make the worst case vanishingly unlikely in practice — but it remains a real, worth-knowing possibility, not a purely theoretical footnote.

How Low Can Sorting Go? The Comparison-Based Lower Bound

Merge sort's O(n log n) isn't just a good result — it's provably close to the best any comparison-based sort can ever achieve. There are n! possible orderings of n distinct elements (Discrete Mathematics Fundamentals' own permutations, Chapter 9 of that course), and each comparison can only rule out at most half the remaining possibilities. Distinguishing among n! orderings therefore needs at least log₂(n!) comparisons in the worst case.

log₂(n!) is itself Θ(n log n)

log₂(n!) and n log₂n grow at the same rate — at n=1,000, log₂(1000!) ≈ 8,529 against 1000 × log₂1000 ≈ 9,966, a ratio of about 0.86 and climbing toward a stable constant as n grows. This means no comparison-based sorting algorithm can ever beat Θ(n log n) in the worst case — merge sort isn't just a good algorithm, it's asymptotically optimal among comparison-based approaches.

Searching & Sorting in Code

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    steps = 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid, steps
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

arr = list(range(1, 16))
print(binary_search(arr, 12))  # (11, 2) — index 11, found in 2 steps

# Comparison-based lower bound, for any n
import math
def min_comparisons_needed(n):
    return math.log2(math.factorial(n))

print(min_comparisons_needed(1000))  # ~8529 -- close to 1000*log2(1000) ~ 9966

Hands-On Exercises

Exercise 1

Trace binary search on the sorted array [3, 7, 11, 15, 19, 23, 27, 31] (8 elements) searching for the target 23. Show each step's lo, hi, mid, and decision, following this chapter's own trace format, and state the total number of comparisons needed.

📄 View solution

Exercise 2

Using this chapter's own measured bubble-sort-vs-merge-sort table, estimate roughly how large the comparison-count gap would be at n = 10,000 if the pattern of widening ratios continues (you don't need to run the code — reason from how the ratio grew between the three given data points). Explain your reasoning.

📄 View solution

Exercise 3

A teammate says "quicksort is always faster than merge sort since it's the industry-standard fast sort." Using this chapter's own quicksort caveat and Chapter 4's own best/worst-case distinction, explain what's missing from this claim, and describe one concrete situation where quicksort's real-world performance could disappoint.

📄 View solution

Chapter 7 Quick Reference

Binary search: Θ(log n), requires sorted input — a 15-element array searched in just 2 comparisons
Bubble sort: O(n²); merge sort: O(n log n) — measured directly, the gap widened from 1.9× to 57.4× going from n=10 to n=1,000
Quicksort: O(n log n) average case, but a genuine O(n²) worst case with poor pivot choices — real implementations guard against this, but it's not purely theoretical
Comparison-based lower bound: Ω(n log n) — no comparison sort can ever beat this, since distinguishing n! orderings needs at least log₂(n!) comparisons, and log₂(n!) is itself Θ(n log n)
Merge sort is therefore asymptotically optimal among comparison-based sorts, not just "pretty good"
Next chapter: Space complexity and amortized analysis