Exercise 2: Best Case vs. Worst Case for a Linear Scan — Possible Solution
====================================================================

THE TEST
------------------------------
    rows = build_rows(5000)
    _, first_comparisons = linear_scan_find(rows, 0)      # the FIRST row's own id
    _, last_comparisons  = linear_scan_find(rows, 4999)   # the LAST row's own id

RESULT
------------------------------
    finding the first row: 1 comparison
    finding the last row:  5000 comparisons

A 5000x difference between the two, on the exact same table.

WHY THE TWO COUNTS DIFFER SO DRAMATICALLY
------------------------------
linear_scan_find walks the list from the beginning, checking one row
at a time and stopping the instant a match is found:

    for row in rows:
        comparisons += 1
        if row['id'] == target_id:
            return row, comparisons

Searching for id=0 (the first row in the list) matches on the very
first comparison -- the loop returns immediately, having done the
absolute minimum possible amount of work. Searching for id=4999 (the
last row) means every single row before it fails to match, so the
loop has to walk all the way to the end -- 5000 comparisons, checking
literally every row in the table, before finally finding what it was
looking for on the last possible check.

WHY A REAL DATABASE CAN'T RELY ON THE BEST CASE
------------------------------
A performance GUARANTEE has to describe what happens in the worst
case an application might actually encounter, not what happens if the
data happens to be arranged favorably. Real queries don't get to
choose which row they're looking for, and there's no reason to expect
the row being searched for is usually near the front of the table --
in practice, a query is just as likely to be looking for a recently-
inserted row (which, in an append-only list, sits at the END) as an
early one. A database that only performed well in the lucky case
would be unpredictable and untrustworthy in exactly the situations
where predictable performance matters most -- so the honest, useful
number to reason about and optimize is the WORST case: O(n)
comparisons for ANY row in a plain linear scan, which is exactly the
number a real B-tree index (Chapters 5-6) is built to replace with a
guaranteed O(log n), regardless of which specific row is being looked
for.

WHY THIS WORKS AS AN ANSWER
------------------------------
This demonstrates that "a linear scan is O(n)" isn't merely a
theoretical classification -- it specifically describes the WORST
case, and the actual cost for any individual lookup can range anywhere
from 1 comparison up to n, entirely depending on where in the table
the matching row happens to sit. Big-O notation, used correctly, is
shorthand for exactly this kind of worst-case guarantee, not a claim
that every operation costs the same.