Capstone — Analyzing and Comparing Real Algorithms

The obvious first approach: check every pair of elements for a match. Before writing any code, Chapter 2's own dominant-term intuition already previews the shape — comparing every element against every other element is going to land in the O(n²) family, the same shape as any nested "compare all pairs" structure.

Avoiding double-counting each pair, the brute-force approach compares element i against every element j > i — exactly Chapter 3's own triangular loop pattern. Total comparisons: n(n−1)/2. On a real test list of n = 1,000 IDs (with 50 genuine duplicates planted in): 499,500 comparisons — matching 1000×999/2 exactly.

Best case: the very first two elements checked happen to be duplicates — found in a single comparison, Θ(1). Worst case: no duplicates exist at all, forcing every one of the n(n−1)/2 comparisons to run to completion — Θ(n²). The 499,500-comparison run above is the worst case, since it never gets to skip ahead once a match streak is found.

A divide-and-conquer idea: split the list in half, recursively find duplicates within each half, then separately handle duplicates that span across the two halves. In the shape Chapter 5 established: T(n) = 2T(n/2) + [cost of the cross-half check] — everything hinges on how cheaply that cross-half step can be done.

If each half is sorted before combining — exactly merge sort's own merge step — checking for duplicates spanning the boundary becomes a single O(n) linear pass. That gives T(n) = 2T(n/2) + O(n) — Chapter 6's own Master Theorem Case 2, resolved instantly: Θ(n log n), with no new derivation needed.

This resolves into a clean two-step algorithm: sort the list (O(n log n), using merge sort specifically — Chapter 7's own measured comparison counts showed it decisively beating bubble sort's O(n²) at any real scale), then a single linear scan checking each element against its neighbor for a match. On the same 1,000-ID test list: the scan itself takes just 999 comparisons, plus roughly 9,966 for the sort — both dramatically below brute force's 499,500.

A hash set offers a third option entirely: scan the list once, checking whether each element is already in a hash set before adding it — average-case O(1) per check (Chapter 4's own hash table discussion), giving O(n) total time. On the same test list: exactly 1,000 operations, one per element — even faster than sort-then-scan. But per Chapter 8's own auxiliary-space accounting, this approach needs a full O(n) hash set alongside the original list — a real memory cost the brute-force approach (needing only O(1) extra space) never pays.

No — and this is provable without any deep complexity theory. Any correct algorithm for this problem must examine every element at least once (an unexamined element could always be the one hiding a duplicate), so Ω(n) is an unavoidable floor for any approach. The hash-set method's O(n) is therefore asymptotically optimal — a genuinely different, tighter lower bound than Chapter 7's own Ω(n log n) for comparison-based sorting, since this problem doesn't require comparison-based sorting at all. And unlike Chapter 9's own traveling-salesman example, this problem sits comfortably in P — efficiently solvable, no NP-completeness in sight.