Operation Counts, Bit Costs, and Measurements

This extension prevents a common engineering error: using one kind of evidence to claim another. Prerequisites are asymptotic notation, recurrence analysis, and the executable labs. Allow 2–3 hours including the short evidence memo.

Three different claims

An exact operation count follows from a specified program and model. An asymptotic bound quantifies over all sufficiently large inputs in a stated family. A benchmark observes runtime for particular inputs, implementations, and machines. A timing doubling ratio near2 can suggest linear growth over the tested range, but cannot establish a universal O(n) bound.

The lab counts element copies, writes, and search comparisons. It does not measure allocation, garbage collection, network delay, or bytes moved. Do not attach milliseconds to those counts. If latency matters, measure those omitted mechanisms separately.

Input size is not always a numeric value

Capacity W written in binary occupies Theta(log W) bits. A knapsack DP doing O(nW) operations is pseudo-polynomial, not necessarily polynomial in encoded input length. Similarly, exact Fibonacci numbers need Theta(n) bits. An algorithm using two integer variables has constant slot count, while its bit storage grows; arbitrary-precision addition is not a unit-cost primitive for unbounded n.

Declare whether the model assumes fixed-size machine words, bounded integers, arbitrary-precision arithmetic, or expensive comparisons such as long strings. The lab's scheduling analysis counts integer comparisons/additions as unit cost; generalizing to huge integer endpoints changes the detailed cost.

Include setup and returned output

For q searches, comparing q scans against one prebuilt hash table differs from rebuilding the table before every query. Account for setup consistently. There is no universal query-count crossover: costs depend on hashing, input size, successful versus failed lookups, and reuse.

In weighted scheduling, a table cell containing a copied full schedule can take linear space per cell. Store scalar scores and predecessor decisions, then reconstruct once. The specification includes original indices; proving only the optimal value leaves the returned witness unverified.

A defensible experiment

Choose a question before timing, such as whether indexed lower-bound search beats repeated full scans for a particular static workload. Fix data sizes, distribution, hit rate, duplicates, setup policy, and equivalent output semantics. Check correctness first. Record Python version and hardware, warm up consistently, repeat batches, and report dispersion as well as a center. Avoid treating all queries within one warm-cache process as independent experiments.

Keep results even when they contradict the expected winner. Explain whether setup, interpreter overhead, cache, or comparison cost could account for the outcome; additional measurements are needed to distinguish those explanations. A benchmark does not prove a CPU-cache mechanism merely because the numbers fit that story.

Memo and acceptance

Write one page separating (1) a proved bound from Lab A or B, (2) the assumptions that bound uses, (3) the finite evidence the checker provides, and (4) a concrete benchmark design with setup, workload, repetitions, and limits. You may execute the benchmark, but do not invent timings if you have not. Include the bit-size and witness-copying caveats above.

Pass: the four claims are distinguishable and no finite table is presented as a universal proof. Repair: provide a function that matches a linear model on every tested n but becomes quadratic beyond the maximum tested size. Explain why no additional finite sample eliminates this possibility by itself.