Exercise 2: The Binary-Search-Plus-Sorted-Insertion Approach — Possible Solution
====================================================================

THE PROPOSED APPROACH
------------------------------
For each of the n elements, use binary search to check whether it
already exists in a separately maintained sorted list (O(log n) per
check, per this chapter's own Step 6 / Chapter 7 material), and if
not found, insert it into the correct sorted position.

STEP 1: THE COST OF THE SEARCH STEP
------------------------------
Binary search on a sorted list of up to n elements costs O(log n) per
check. Done once per each of the n input elements:

  Total search cost: O(n log n)

STEP 2: THE COST OF THE INSERTION STEP
------------------------------
Per Chapter 4's own sorted-array insertion exercise, inserting into a
sorted array/list at an arbitrary position requires shifting existing
elements to make room - in the worst case (inserting near the
beginning), this is O(n) per insertion, not O(log n). Done once per
each of the n input elements:

  Total insertion cost, worst case: O(n) x n = O(n^2)

STEP 3: THE OVERALL TIME COMPLEXITY
------------------------------
Total = O(n log n) [searching] + O(n^2) [inserting]

Per this chapter's own dominant-term reasoning (from Chapter 2), the
O(n^2) term dominates the smaller O(n log n) term:

  Overall: O(n^2)

STEP 4: HONEST COMPARISON TO THE HASH-SET APPROACH
------------------------------
Despite using a genuinely efficient O(log n) search technique, this
approach's overall Big-O class is O(n^2) - the SAME class as the
original brute-force approach (Steps 2-3), not an improvement over
it at all. The efficient-looking binary search step doesn't rescue
the algorithm, because the sorted-list insertion step it depends on
is itself expensive. This is strictly worse than the hash-set
approach's O(n) average time, despite superficially "sounding smarter"
by using binary search.

WHY THIS WORKS AS AN ANSWER
------------------------------
Each of the two costs (searching and inserting) is analyzed
separately using material directly from this course (Chapter 7's
binary search, Chapter 4's sorted-insertion exercise), the dominant
term is identified using Chapter 2's own rule, and the honest
conclusion - that a clever-sounding piece within an algorithm doesn't
automatically make the whole algorithm efficient - is stated
explicitly rather than assumed.