Algorithms and complexity

An algorithm is a precise strategy for transforming input into output. Good algorithm design starts with correctness and constraints, then considers how runtime and memory grow as inputs grow.

A disciplined design process

1. Define input, output, and invalid cases.
2. Write examples, including empty, minimal, duplicate, and extreme inputs.
3. State invariants—the facts that remain true during execution.
4. Solve the simplest version clearly.
5. Analyze time and auxiliary space.
6. Measure with representative data when performance matters.

For a function that returns the first duplicate, decide whether values are hashable, whether input order matters, and what happens when no duplicate exists before choosing an approach.

from collections.abc import Hashable, Iterable
from typing import TypeVar

T = TypeVar("T", bound=Hashable)


def first_duplicate(values: Iterable[T]) -> T | None:
    seen: set[T] = set()
    for value in values:
        if value in seen:
            return value
        seen.add(value)
    return None

Expected set lookup is constant time, so the algorithm is expected O(n) time and O(n) additional space. The simpler nested-loop solution is O(n²) time and O(1) extra space.

Common growth rates

• O(1): direct indexing or a bounded operation;
• O(log n): repeatedly halving a sorted search range;
• O(n): scanning all items once;
• O(n log n): efficient comparison sorting;
• O(n²): comparing every pair;
• O(2ⁿ) or O(n!): exhaustive combinatorial search.

Big-O describes growth, not elapsed seconds. O(n) code can be slower than O(n log n) for small inputs because constants, allocation, cache behavior, Python-level loops, and I/O matter.

Analyze sequences of work

Drop constants and lower-order terms:

def summarize(values: list[int]) -> tuple[int, int]:
    total = sum(values)        # O(n)
    maximum = max(values)      # O(n)
    return total, maximum

Two scans produce O(2n), simplified to O(n). If the input may be empty, the contract must address max() before complexity matters.

Nested loops are not automatically quadratic. Consider their ranges:

def count_halvings(limit: int) -> int:
    steps = 0
    value = limit
    while value > 1:
        value //= 2
        steps += 1
    return steps

This is O(log n) because each iteration halves the remaining magnitude.

Space complexity

Track memory that grows with input. A set of all visited values is O(n) auxiliary space. A generator can reduce peak memory:

from collections.abc import Iterable, Iterator


def positive_squares(values: Iterable[int]) -> Iterator[int]:
    for value in values:
        if value > 0:
            yield value * value

Streaming does not make total work disappear, and one-shot iterators cannot be restarted. Document whether a function accepts any iterable or requires a reusable sequence.

Choose the right data structure

• list: ordered sequence, fast append and indexed access, linear membership;
• deque: fast insertion and removal at both ends;
• set: expected fast membership and uniqueness, no positional indexing;
• dict: expected fast key lookup and insertion-order preservation;
• heapq: fast access to the smallest item, useful for top-k and scheduling;
• bisect: binary search over a sorted list, though insertion remains linear.

Changing a data structure often improves complexity more safely than rewriting control flow.

Correctness tools

For loops, write an invariant such as: “Before each iteration, seen contains exactly the values before the current position.” For recursive algorithms, define a base case and prove that each call moves toward it. Python's recursion depth makes iterative solutions preferable for deeply nested or unbounded inputs.

Pitfalls

• analyzing only the happy path;
• assuming hash operations are guaranteed O(1) rather than expected O(1);
• ignoring the cost of slicing, copying, sorting, or string concatenation;
• optimizing for theoretical scale that the application never reaches;
• using recursion where input depth is uncontrolled;
• benchmarking setup or I/O instead of the operation of interest.

Analysis checklist

• Input size and constraints are defined.
• Edge cases and failure behavior are explicit.
• Time and auxiliary space are analyzed.
• Built-in operation costs are included.
• The selected data structure matches required operations.
• Performance claims are measured on representative inputs.
• Clarity is preserved unless evidence justifies complexity.

Practice

Implement a frequency counter first with a list of (value, count) pairs and then with a dictionary. Analyze both approaches for n input items and k distinct values. Benchmark several values of n, explain where the measurements diverge from the simplified model, and retain the clearer implementation that meets the actual requirement.