Exercise 3: log2(n) vs. a Linear Scan's Own Worst Case, at Four Sizes — Possible Solution
====================================================================

THE TEST
------------------------------
    for n in (1000, 10000, 100000, 1000000):
        log_n = math.log2(n)
        # compare against n itself, the linear scan's own worst-case comparisons

RESULT
------------------------------
    n=1,000       linear scan: 1,000 comparisons        log2(n) =~ 10.0
    n=10,000      linear scan: 10,000 comparisons        log2(n) =~ 13.3
    n=100,000     linear scan: 100,000 comparisons        log2(n) =~ 16.6
    n=1,000,000   linear scan: 1,000,000 comparisons      log2(n) =~ 19.9

HOW THE GAP CHANGES AS THE TABLE GROWS
------------------------------
Each row of the table represents the SAME 10x growth in table size
(1,000 -> 10,000 -> 100,000 -> 1,000,000). The linear scan's own
column grows by exactly that same 10x factor every single row --
1,000 to 10,000 is a 10x increase, 10,000 to 100,000 is another 10x
increase, and so on, without exception, because a linear scan's cost
IS the table size.

The log2(n) column, by contrast, grows by only about 3.3 EXTRA
comparisons each time the table grows 10x (10.0 -> 13.3 -> 16.6 ->
19.9 -- each step is +3.32, since log2(10) =~ 3.32). The absolute
number of comparisons a real B-tree needs barely moves at all, even
as the table itself grows by a full order of magnitude, again and
again.

The RATIO between the two columns -- how many times worse a linear
scan is compared to a B-tree, at each size -- widens dramatically:
100 (=1000/10) at n=1,000; about 752 at n=10,000; about 6,024 at
n=100,000; about 50,251 at n=1,000,000. The advantage a real index
provides isn't a fixed, one-time speedup -- it's an advantage that
keeps compounding, becoming more and more dramatic the larger the
table gets.

WHY THIS WORKS AS AN ANSWER
------------------------------
This is the real, concrete meaning behind the abstract claim "O(log n)
beats O(n)" -- it isn't just that log n is a smaller number than n; it's
that the GAP between the two grows without bound as n grows, meaning
the case for building a real index gets stronger, not weaker, exactly
as a table becomes large enough that performance actually starts to
matter in practice. A table small enough to fit comfortably in memory
might never notice the difference; a table large enough to be a real
production concern is exactly where this gap becomes enormous.