Exercise 2: Estimating the Gap at n=10,000 — Possible Solution
====================================================================

GIVEN DATA POINTS
------------------------------
n=10:    ratio ~= 1.9x
n=100:   ratio ~= 9.3x
n=1,000: ratio ~= 57.4x

REASONING FROM THE FORMULAS DIRECTLY
------------------------------
Bubble sort's comparison count grows as roughly n^2/2 (per Chapter 3's
own triangular-loop analysis), while merge sort's grows as roughly
n*log2(n) (Chapter 6's own Master Theorem result). The ratio between
them is therefore approximately:

  ratio(n) ~= (n^2/2) / (n log2 n) = n / (2 log2 n)

Checking this formula against the given data points:
  n=10:    10 / (2 x log2(10)) = 10 / (2 x 3.32)  ~= 1.5   (roughly matches ~1.9x)
  n=100:   100 / (2 x log2(100)) = 100 / (2 x 6.64) ~= 7.5  (roughly matches ~9.3x)
  n=1000:  1000 / (2 x log2(1000)) = 1000 / (2 x 9.97) ~= 50.2 (roughly matches ~57.4x)

The formula tracks the same growth pattern as the measured data
reasonably well (some gap is expected, since the formula uses
simplified average-case approximations rather than the exact measured
counts).

ESTIMATING AT n=10,000
------------------------------
ratio(10,000) ~= 10,000 / (2 x log2(10,000)) = 10,000 / (2 x 13.29)
              ~= 10,000 / 26.58
              ~= 376

So the gap at n=10,000 would plausibly grow to somewhere in the range
of several hundred times - dramatically larger than the 57x gap
already seen at n=1,000, since the ratio itself keeps growing (roughly
proportionally to n divided by a slowly-growing log n term) as n
increases further.

WHY THIS WORKS AS AN ANSWER
------------------------------
Rather than guessing, the estimate is derived from the underlying
growth-rate formulas this chapter and Chapter 6 already established
for each algorithm (n^2/2 for bubble sort, n log2 n for merge sort),
cross-checked against the three given measured data points to confirm
the formula's own pattern roughly matches reality, before extrapolating
it forward to n=10,000.