Exercise 2: Counting Real Operations — Possible Solution
====================================================================

THE TEST
------------------------------
    def nested_loop_join_counted(left_rows, left_key_idx, right_rows, right_key_idx):
        comparisons = 0
        for l in left_rows:
            for r in right_rows:
                comparisons += 1
                if l[left_key_idx] == r[right_key_idx]:
                    ...
        return results, comparisons

    def hash_join_counted(build_rows, build_key_idx, probe_rows, probe_key_idx):
        build_steps = 0
        for row in build_rows:
            build_steps += 1
            ...
        probe_steps = 0
        for probe_row in probe_rows:
            probe_steps += 1
            ...
        return results, build_steps + probe_steps

    _, comparisons = nested_loop_join_counted(customers, 0, orders, 1)   # 3 customers, 4 orders
    _, hj_steps = hash_join_counted(customers, 0, orders, 1)

RESULT
------------------------------
    real comparison count for 3 customers x 4 orders: 12
    real build+probe step count for the same data: 7

Nested-loop needs exactly 12 comparisons. Hash join needs exactly 7
steps (3 build steps + 4 probe steps).

WHY THE NUMBERS MATCH THE BIG-O ANALYSIS EXACTLY, NOT APPROXIMATELY
------------------------------
Nested-loop's own comparisons counter increments exactly once per
iteration of the inner loop, and the inner loop runs len(right_rows)
times for every single row in left_rows -- giving exactly
len(left_rows) * len(right_rows) = 3 * 4 = 12 total increments, with
no rounding, no approximation, and no dependence on how many of those
comparisons happen to match.

Hash join's own step counters are split into two independent phases:
build_steps increments once per row in build_rows (3, one per
customer), and probe_steps increments once per row in probe_rows (4,
one per order) -- regardless of how many matches each probe actually
finds, since the counter increments BEFORE the inner "for build_row
in hash_table.get(key, [])" loop even runs. The total is exactly
3 + 4 = 7, matching rows_left + rows_right precisely.

WHY THIS IS A MEANINGFULLY STRONGER CLAIM THAN "HASH JOIN IS FASTER"
------------------------------
Finding 2's own real-world timing measurement (0.0147s vs. 0.0003s)
is a genuine, honest measurement, but real wall-clock time is also
affected by things that have nothing to do with algorithmic
complexity -- Python's own interpreter overhead, dict hashing cost per
key, CPU cache behavior. Counting the actual number of logical
operations performed, independent of how fast any one operation
happens to run, isolates the O(n*m) vs. O(n+m) claim from all of
that -- confirming the two algorithms genuinely do a different AMOUNT
of work, not just that one happens to run faster on this particular
machine.

WHY THIS WORKS AS AN ANSWER
------------------------------
Verifying the exact comparison/step counts at a small, hand-checkable
scale (3 x 4, not 800 x 800) means the numbers can be confirmed by
direct arithmetic rather than trusted on faith -- 3*4=12 and 3+4=7 are
both easy to verify independently, which is exactly what makes this a
stronger confirmation of the underlying complexity claim than the
chapter's own larger-scale timing test alone.