Algorithms: count the work before buying capacity

Consider finding a request ID in a collection. Does the collection contain duplicates? Must the result include every match, the first match, or simply a yes-or-no answer? Is the input sorted, and who pays to keep it sorted? These choices change both correctness and cost. A fast method that silently relies on an absent ordering property is an incorrect method, not an optimization with an unusual edge case.

An invariant is a statement maintained as an algorithm proceeds. A linear search can maintain that all earlier items have been inspected without finding a match. Binary search maintains a smaller interval that contains any remaining possible match. Writing the invariant helps explain why the answer is justified and why the loop terminates. It also suggests tests for empty input, one element, duplicate boundaries, and missing targets.

Big-O describes an upper growth bound as input size becomes large. It does not say that every operation has equal cost, or that one implementation is faster at every size. A quadratic all-pairs comparison examines a number of pairs proportional to the square of the input size. Doubling the size can approximately quadruple that work. A linear pass approximately doubles its work under the same change.

Do not confuse average behavior with a worst-case guarantee. A lookup structure can perform well for representative keys while still having expensive exceptional cases or resize events. Memory usage and preprocessing are part of the tradeoff: building an index has a cost that may be worthwhile across repeated queries. For AI pipelines, reducing redundant data scans can matter more than speeding up a single arithmetic operation. Measure the whole repeated workflow.

Benchmark realistic sizes and distributions, record hardware and software versions, and separate startup from steady work when both matter. Report variability rather than a single conveniently low number. A dataset that fits in a cache may behave very differently once enlarged. Complexity predicts a possible growth trend; a benchmark estimates behavior under its documented conditions. Neither replaces the other, and neither proves correctness.

The lab fixes the growth shape to $y=ax^2$: change coefficient $a$ and move position $x$. At positive $a$, doubling positive $x$ quadruples the modeled output. Interpret that as an all-pairs work illustration with normalized input size, not a timing benchmark. The controls cannot switch to a linear or logarithmic algorithm. Explain why this quadratic growth creates a capacity risk. Finally, ask whether a different data structure, batching approach, or problem formulation reduces the work before considering extra machines.