Data Structures & Algorithms / Contracts, sequences, and search / Lesson 1

Contracts, invariants, and cost models

Prove what a loop computes, count the work it performs, and state the assumptions behind asymptotic claims.

About 5 min readContent reviewed 2026-10-28

On this page

Lesson goals

State the problem before choosing a container
An invariant connects partial work to the goal
Count work from the actual loop bounds

State the problem before choosing a container

An algorithm needs an input contract, a result contract, and a resource model. Finding any matching pair is different from counting all matching pairs, and returning positions is different from returning values. Decide whether duplicate values represent distinct records and whether input may be mutated. These choices change both correctness and useful data structures. For the course, examples use small synthetic Python3 sequences, deterministic output, and no external services. Complexity explanations usually count primitive comparisons or accesses under a unit-cost model; large-integer arithmetic and expensive user-defined comparisons require additional accounting.

An invariant connects partial work to the goal

A loop invariant is a property true before the first iteration and preserved by every iteration. At termination it should imply the promised result. The first example maintains that total is the sum of exactly the elements already visited and visits is their count. Initialization handles the empty prefix, each addition extends the prefix by one value, and termination covers the full sequence. An invariant is more useful than a comment saying add numbers because it explains why no element is omitted or counted twice and makes the empty-input result explicit.

python Self-contained Python3 algorithm example using synthetic local data.

def measured_sum(values):
    total = 0
    visits = 0
    for value in values:
        total += value
        visits += 1
    return total, visits

print(measured_sum([1, 2, 3, 4]))
print(measured_sum([]))

Expected output

(10, 4)
(0, 0)

One iteration processes one value. The counted visits equal input length; this is an operation-count illustration, not a timing benchmark.

Count work from the actual loop bounds

The second example visits every unordered pair of distinct positions once. For a sequence of length n, the inner counts are n-1, n-2, through zero, totaling n(n-1)/2. That is quadratic growth even though there is no explicit multiplication in the program. The j > i boundary prevents pairing an element with itself and prevents counting the same positional pair in both orders. Duplicate values can still participate in distinct positional pairs. The returned match count therefore follows the stated positional contract, which a set-based deduplication would change.

python Self-contained Python3 algorithm example using synthetic local data.

def pair_counts(values, target):
    checks = matches = 0
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            checks += 1
            if values[i] + values[j] == target:
                matches += 1
    return checks, matches

print(pair_counts([2, 4, 7, 9], 11))
print(pair_counts([5], 10))

Expected output

(6, 2)
(0, 0)

The two matching pairs are positions (0,3) and (1,2). A single 5 cannot pair with itself.

Separate upper bounds, tight bounds, and cases

Big O gives an asymptotic upper bound, while Theta expresses a matching upper and lower growth order under the chosen model. A linear algorithm is also O(n squared), so an unnecessarily loose upper bound can be true but unhelpful. Specify worst case, best case, expected case, or amortized cost rather than using them interchangeably. Early exit can make the best case constant while the worst case remains linear. Expected hashing behavior depends on assumptions and differs from amortized dynamic-array resizing. Always name the input quantity: vertices and edges are not the same variable.

Account for memory and hidden language work

A result list containing n values needs space proportional to n even if the loop uses only two local variables. A slice usually creates a new Python list, and repeated slicing inside recursion can add copying work not visible in a recurrence that counts comparisons only. Calling a helper once per iteration does not make that helper constant time. Include input representation, output size, and auxiliary storage separately. Python integers can grow in bit length, so summing enormous values has arithmetic costs beyond a simplistic fixed-word model. State the simplified model before using it.

Use tests as counterexample search, not a proof substitute

Test empty input, one element, duplicates, boundary positions, and a normal example chosen to expose the contract. Compare a faster algorithm against a simple reference implementation on small exhaustive inputs when practical. This is useful differential evidence, but a finite test set does not prove every possible input. Combine invariants and termination arguments with tests that would distinguish likely mistakes. Count operations to study growth before measuring tiny wall-clock intervals, which may be dominated by interpreter and scheduling overhead. The course validates safe local programs without load testing or external resources.

Common errors and fixes

Nested loops are called linear because each line is simple

Why it happens: The total iteration count was not summed.
How to fix it: Derive the sum from the actual bounds.
Prevent it next time: Count operations on small n and compare the formula.

A pair uses the same position twice

Why it happens: The contract for distinct positions was not encoded in bounds.
How to fix it: Require j greater than i or another proven distinct-index rule.
Prevent it next time: Test a single matching half-value.

A helper hides extra linear copying

Why it happens: Only the visible loop body was counted.
How to fix it: Inspect helper, slicing, and allocation costs.
Prevent it next time: State the cost model with the algorithm.

Check your understanding

1. What invariant proves measured_sum for an empty list?

Show worked solution

Before processing anything, total is the sum of the empty prefix, zero, and visits is zero. The loop performs no iterations, so that invariant already covers the complete input. The result (0,0) follows without an exceptional special case.

2. How many pair checks occur for five elements under pair_counts?