Complexity and contracts

Explanation

Count the operations that grow with input size. One scan is linear; enumerating every pair is quadratic. A formula can sometimes compute a count without enumerating its members. Big-O ignores constant factors but does not erase input validation or output costs.

State n precisely, distinguish worst-case from expected behavior, and include auxiliary versus output space. Compare equivalent contracts before comparing algorithms.

Runnable worked example

function solve(values, threshold) { return values.filter(v => v > threshold).length; }

const result = solve([1, 2, 2, 3], 2);
if (JSON.stringify(result) !== "1") throw new Error("Example failed");

Expected result: 1.

Inspect each element once. The number of inspections grows linearly, including when no value matches. O(n) time; Python O(1) extra space, JavaScript filter O(n) extra space.

Common mistakes

Do not claim constant space for a returned list or logarithmic performance merely because a loop contains division.

Guided practice

Trace the example by hand and name the invariant after each update. Add a boundary case that would break a plausible incorrect implementation. Explain termination and the largest working structure before claiming a complexity bound.

Independent practice

• Count predicate matches
• Count index pairs

Recap

Relate input size to work and distinguish runtime from output size. Contracts, invariants, boundary tests, and complexity reasoning work together. The Python and JavaScript tracks cover corresponding algorithmic concepts with language-specific implementations and independent progress.