Verifying and benchmarking algorithms

Test against a brute-force oracle, use property-based tests, generate adversarial inputs, and measure runtime without fooling yourself.

Brute force as an oracle

import itertools
import random
from typing import Callable, Sequence

def brute_force_lis(nums: Sequence[int]) -> int:
    """The oracle: check every subsequence. Exponential, and obviously correct."""
    n = len(nums)
    best = 0
    for r in range(n + 1):
        for idx in itertools.combinations(range(n), r):
            values = [nums[i] for i in idx]
            if all(values[i] < values[i + 1] for i in range(len(values) - 1)):
                best = max(best, len(values))
    return best


def differential_test(
    candidate: Callable[[Sequence[int]], int],
    oracle: Callable[[Sequence[int]], int],
    trials: int = 500,
    seed: int = 12345,
) -> None:
    """Randomised inputs, both implementations, compare. The highest-value test
    for an algorithm, because it needs no expected values written by hand."""
    rng = random.Random(seed)          # a fixed seed makes a failure reproducible
    for t in range(trials):
        n = rng.randint(0, 9)
        xs = [rng.randint(-5, 5) for _ in range(n)]
        got = candidate(xs)
        want = oracle(list(xs))
        if got != want:
            raise AssertionError(f"trial {t}: input={xs} got={got} want={want}")
    print(f"{trials} trials passed")


def edge_cases(candidate: Callable[[Sequence[int]], int]) -> None:
    """The inputs a random generator will almost never produce."""
    for xs in ([], [0], [1, 1, 1], [-1, -2, -3], list(range(50)), list(range(50, 0, -1))):
        candidate(xs)


if __name__ == "__main__":
    from bisect import bisect_left

    def fast_lis(nums: Sequence[int]) -> int:
        tails: list[int] = []
        for x in nums:
            i = bisect_left(tails, x)
            if i == len(tails):
                tails.append(x)
            else:
                tails[i] = x
        return len(tails)

    differential_test(fast_lis, brute_force_lis)
    edge_cases(fast_lis)

• A differential test needs no hand-written expectations, so it scales to thousands of cases and finds the boundary you did not think of.
• Keep the seed. When a run fails, print the input and re-run with that seed to reproduce it exactly.
• The oracle must be obviously correct rather than fast. A clever oracle is just a second buggy implementation.
• Test the empty input, the single element, all equal, already sorted, reverse sorted, and the maximum size. Random inputs cover none of these well.

Property-based tests

import random
from typing import Sequence

def check_sorted_property(xs: list[int]) -> None:
    """Sorting is idempotent, output length is preserved, and it is ordered."""
    original = list(xs)
    xs.sort()
    assert len(xs) == len(original)
    assert all(xs[i] <= xs[i + 1] for i in range(len(xs) - 1))
    assert sorted(xs) == xs                       # idempotent
    assert sorted(original) == xs                 # a permutation, same multiset
    assert sum(xs) == sum(original)               # sums agree


def check_dijkstra_property(n: int, adj: dict[int, list[tuple[int, int]]]) -> None:
    """Triangle inequality: no shortcut through v is cheaper than going direct.
    Any shortest-path implementation must satisfy this."""
    dist = dijkstra(n, adj, 0)
    for u in range(n):
        if dist[u] == float("inf"):
            continue
        for v, w in adj.get(u, ()):
            assert dist[v] <= dist[u] + w, f"edge {u}->{v} violates the bound"


def check_union_find_property(n: int, unions: list[tuple[int, int]]) -> None:
    """Connectivity must be an equivalence relation: reflexive, symmetric,
    transitive. Transitivity is the one a buggy implementation breaks."""
    dsu = DSU(n)
    for a, b in unions:
        dsu.union(a, b)
    for a, b, c in zip(range(n), range(1, n + 1), range(2, n + 2)):
        if b >= n or c >= n:
            break
        if dsu.connected(a, b) and dsu.connected(b, c):
            assert dsu.connected(a, c)


def dijkstra(n: int, adj: dict[int, list[tuple[int, int]]], src: int) -> list[float]:
    import heapq
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj.get(u, ()):
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return dist


class DSU:
    def __init__(self, n: int) -> None:
        self.p = list(range(n))
    def find(self, x: int) -> int:
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]
            x = self.p[x]
        return x
    def union(self, a: int, b: int) -> None:
        ra, rb = self.find(a), self.find(b)
        if ra != rb:
            self.p[rb] = ra
    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

A property test is a specification written as code. "Sorting returns a permutation of the input that is ordered" captures the whole contract in one function, and it is much harder to weaken accidentally than a set of hand-written expected values.

Benchmarking that does not lie

import random
import timeit
from typing import Callable, Sequence

def measure(fn: Callable[[], None], repeat: int = 7) -> float:
    """timeit handles the warm-up, takes the best of several runs, and disables
    the garbage collector between them. Best-of is the right statistic for a
    CPU-bound benchmark: the noise is one-sided."""
    return min(timeit.repeat(fn, number=1, repeat=repeat))

def compare(candidates: dict[str, Callable[[], None]], scale: int) -> None:
    print(f"n = {scale}")
    baseline = None
    for name, fn in candidates.items():
        t = measure(fn)
        if baseline is None:
            baseline = t
        print(f"  {name:22s} {t*1000:9.3f} ms   {t/baseline:5.2f}x")
    print()

def build_inputs(n: int) -> dict[str, list[int]]:
    """Adversarial inputs matter more than random ones."""
    rng = random.Random(0)
    return {
        "random": [rng.randint(0, 10 * n) for _ in range(n)],
        "sorted": list(range(n)),
        "reversed": list(range(n, 0, -1)),
        "all_equal": [7] * n,
        "almost_sorted": list(range(n)),
    }

if __name__ == "__main__":
    for scale in (1_000, 10_000):
        data = build_inputs(scale)
        compare({
            "sorted builtin": lambda: sorted(data["random"]),
            "sorted on sorted": lambda: sorted(data["sorted"]),
            "sorted on reversed": lambda: sorted(data["reversed"]),
            "sorted on all equal": lambda: sorted(data["all_equal"]),
        }, scale)

• Measure the operation you claim to measure. A benchmark that includes building the input measures input construction as well.
• Compare like with like: same input data, same warm-up, same Python build, same machine, and no debugger attached.
• Report the shape of the growth, not one number. Run at 1,000, 10,000 and 100,000 and check that the ratio matches the complexity you expect.
• A single run on a laptop with a background browser open measures the browser. Use the best of several runs, and re-run when a result looks surprising.
• An asymptotic advantage can lose on real inputs. An O(n log n) algorithm with a large constant can be slower than an O(n squared) one for n below a few hundred; that crossover is worth measuring.

FAQ

Related

Complexity and Big-O in practice String algorithms: matching, hashing and tries

Last refreshed 2026-09-18.