Contracts, Representation, and Performance
An algorithm name does not define its engineering contract. For each implementation write down key ordering, duplicate behavior, allowed mutation, output shape, memory model, errors, and what one counted operation means.
Ordering and identity
A stable sort compares keys while preserving original order among equivalent keys. An explicit secondary key changes the ordering contract. A sequence number is useful when FIFO ties are required across streams or events. Comparing entire records may accidentally compare payloads; include payloads that reject ordering in tests. Keep records intact and check multiplicity, not just sorted key output.
These labs use integer keys and consistent total ordering. A comparator that is nontransitive invalidates partition and merge reasoning. NaN and mixed incomparable types require an explicit policy before extending the contract. Fixed-width signed integer encoding differs from floating-point ordering. Unicode byte order and locale collation are different requirements. Define the requirement before adding a clever representation transformation.
Costs that belong in the model
| Claim | Qualification required |
|---|---|
| Binary search is logarithmic | Random-access cost and sortedness precondition; no hidden linear scan |
| Hash lookup is constant | Hash/equality cost, randomness assumptions, occupancy and adversary model |
| Push is logarithmic | Sift work versus occasional dynamic-array reallocation |
| Selection uses constant extra memory | In-place partition and iteration; a preserved-input copy adds O(n) |
| Merge uses O(K) space | One head and iterator per stream; exclude or include output explicitly |
| Radix is linear | Key width, digit count, bucket initialization, digit extraction |
| External sort needs one pass | Count run generation and every read/write merge stage |
Expected cost averages over randomness; amortized cost bounds an operation sequence; worst-case cost applies to the most expensive allowed instance. Use the qualifiers together only when both analyses have been established. The lab's deterministic modulo hash has no expected-constant-time guarantee.
Three levels of evidence
- Proof: invariant and termination establish a general claim under explicit assumptions. A cost derivation prices operations in a model.
- Executable checks: exhaustive small cases, seeded sequences and deliberate faults find mistakes and counterexamples. They cover finite inputs.
- Measurements: timed representative workloads estimate performance in an environment. They do not establish correctness or an asymptotic theorem.
Keep these separate in the submission. Passing the oracle does not prove the oracle is infallible; inspect small examples independently. A sorted output also needs length, multiplicity and stability checks when the contract requires them.
A reproducible measurement note
Record operating system, hardware, runtime/compiler version, implementation revision, input sizes, input generation and seed. Include random, sorted, reverse, duplicate-heavy and structured adversarial families as appropriate. For tables, test both spread keys and clusters, plus deletion-heavy operation histories. Preserve the generated input and state whether copying, key extraction, allocation and setup are inside the timed region.
Verify correctness outside timing. Use repeated trials, retain raw observations, and report a central value and spread; document warm-up and runtime effects. Compare implementations doing the same work with the same mutation and output contract. Include peak-memory observations or a reasoned estimate. Do not report a speed ratio from a different language implementation as an algorithm theorem. Stop when the experiment answers the stated decision; bigger input is not an automatic sign of rigor.
Transfer beyond the lab
Choose one: add versioned event cancellation; maintain a deletion-heavy table; merge files under a fixed buffer budget; answer repeated rank queries under updates. Identify the old proof that stops applying, the new invariant, the cost change, and the smallest counterexample to an unchanged implementation. Keep file buffering, persistence, concurrency, and crash recovery as explicit added requirements rather than implying the in-memory lab already provides them.