Exercise 3: Mapping Each Worked-Comparison Step to Its Topic — Possible Solution
====================================================================================

STEP 1: PREVIEWING THE BRUTE-FORCE SHAPE BEFORE WRITING CODE — BIG-O
NOTATION: FORMAL DEFINITION & GROWTH RATES (CHAPTER 2)
------------------------------
Recognizing that an all-pairs comparison structure will land in the
O(n^2) family before any code is even written is Chapter 2's own
dominant-term/growth-rate intuition, applied predictively.

STEP 2: COUNTING BRUTE-FORCE COMPARISONS PRECISELY — ANALYZING
LOOPS: FROM CODE TO BIG-O (CHAPTER 3)
------------------------------
Using the triangular-loop summation formula n(n-1)/2 to get an exact
comparison count, rather than just a Big-O label, is directly Chapter
3's own count-the-operations method.

STEP 3: BEST AND WORST CASE FOR BRUTE FORCE — BIG-OMEGA & BIG-THETA:
BEST, WORST & AVERAGE CASE (CHAPTER 4)
------------------------------
Distinguishing the best case (an immediate match) from the worst case
(no duplicates at all, forcing every comparison) is exactly Chapter
4's own best/worst-case framework.

STEP 4: A RECURSIVE ALTERNATIVE AND ITS RECURRENCE — RECURSIVE
ALGORITHMS & RECURRENCE RELATIONS (CHAPTER 5)
------------------------------
Proposing a divide-and-conquer approach and writing its recurrence in
the T(n) = [calls]T([subproblem size]) + [extra work] shape is
Chapter 5's own recurrence-relation material.

STEP 5: RESOLVING THE RECURRENCE VIA THE MASTER THEOREM — SOLVING
RECURRENCES: SUBSTITUTION & THE MASTER THEOREM (CHAPTER 6)
------------------------------
Recognizing the T(n) = 2T(n/2) + O(n) shape and applying the Master
Theorem's Case 2 directly, without re-deriving anything by hand, is
Chapter 6's own fast-path technique.

STEP 6: FORMALIZING SORT-THEN-SCAN AND CHOOSING MERGE SORT OVER
BUBBLE SORT — COMMON COMPLEXITY CLASSES IN PRACTICE: SEARCHING &
SORTING (CHAPTER 7)
------------------------------
Choosing a specific sorting algorithm based on measured comparison-
count evidence, then combining it with a linear scan, is Chapter 7's
own searching-and-sorting material.

STEP 7: THE HASH-SET APPROACH AND ITS SPACE COST — SPACE COMPLEXITY &
AMORTIZED ANALYSIS (CHAPTER 8)
------------------------------
Weighing a faster approach's time advantage against its genuine
auxiliary-space cost is exactly Chapter 8's own space-complexity
accounting.

STEP 8: PROVING NO APPROACH CAN BEAT O(n) — BEYOND POLYNOMIAL TIME:
EXPONENTIAL GROWTH & A TASTE OF P VS. NP (CHAPTER 9)
------------------------------
Arguing for an inherent Omega(n) lower bound (every element must be
examined at least once) and explicitly noting the problem sits in P,
not NP-complete territory, is Chapter 9's own lower-bound and
complexity-classification material.

WHY THIS WORKS AS AN ANSWER
------------------------------
Each step is matched to its topic by identifying the specific
analytical technique actually being used - growth-rate prediction,
precise operation counting, case distinction, recurrence-writing,
Master Theorem application, algorithm selection, space accounting, and
a lower-bound argument - rather than simply repeating the chapter
numbers already given in the original worked comparison.