1.11 Testing Algorithms

Testing does not prove an algorithm correct, but it exposes mistakes in specifications, invariants, edge cases, and implementation details. A good test suite is built from the problem statement. It checks whether the implementation satisfies the input and output contract under ordinary, boundary, and adversarial conditions.

Algorithm tests should not only ask, “Does this example pass?” They should ask, “What assumption would fail if this test failed?” Each test should have a reason.

Problem

You have an algorithm and need a reliable way to test whether the implementation matches the specification.

Solution

Build tests from five sources:

1. Minimal valid inputs
2. Boundary cases
3. Ordinary representative cases
4. Adversarial cases
5. Random cases checked against a simple baseline

The strongest practical pattern is to pair an efficient algorithm with a slow, obviously correct implementation. The slow implementation acts as an oracle for small inputs.

Example: Maximum Subarray Sum

Specification:

Given a nonempty integer array A, return the maximum sum of any nonempty contiguous subarray.

Efficient algorithm:

max_subarray(A):
  best = A[0]
  current = A[0]

  for i = 1 to n - 1:
    current = max(A[i], current + A[i])
    best = max(best, current)

  return best

Baseline algorithm:

max_subarray_slow(A):
  best = A[0]

  for left = 0 to n - 1:
    sum = 0
    for right = left to n - 1:
      sum = sum + A[right]
      best = max(best, sum)

  return best

The slow algorithm tries every subarray, so it directly matches the specification. It is too slow for large input, but it is useful for testing small input.

Fixed Tests

Start with examples that target known boundary conditions.

[5]                  -> 5
[-5]                 -> -5
[-5, -2, -8]         -> -2
[0, 0, 0]            -> 0
[4, -1, 2, -7, 3]   -> 5
[1, 2, 3]            -> 6
[-1, 5, -1]          -> 5

Each test exists for a reason. The all-negative case checks initialization. The all-zero case checks neutral values. The increasing case checks that the whole array may be optimal. The last case checks that extending a subarray can be worse than restarting.

Random Testing

For small arrays, compare the efficient algorithm against the baseline.

for trial = 1 to 10000:
  n = random integer from 1 to 10
  A = random array of length n with values from -20 to 20

  assert max_subarray(A) == max_subarray_slow(A)

Random testing is effective because it explores many combinations that humans do not naturally write. It is especially useful for algorithms with many branches, such as dynamic programming, graph traversal, and pointer manipulation.

Metamorphic Tests

Some properties can be tested even without knowing the exact answer. These are called metamorphic properties.

For maximum subarray sum:

If every element is increased by a nonnegative constant,
the answer should not decrease.

For sorting:

sort(sort(A)) = sort(A)

For shortest paths with nonnegative edge weights:

Removing an edge cannot make the shortest path shorter.

For set union:

union(A, B) = union(B, A)

These tests do not replace exact expected values, but they add coverage across broad input families.

Testing Invariants

When possible, test internal invariants during execution. For example, in binary search, the current interval should always contain every possible remaining answer. In a heap, every parent should satisfy the heap property with respect to its children. In union-find, parent pointers should eventually lead to a representative.

Invariant checks are often too expensive for production, but they are useful in debug builds.

assert heap_property(H)
assert 0 <= left and right < n
assert distance[v] <= distance[u] + weight(u, v)

These assertions turn vague assumptions into executable checks.

Adversarial Tests

Adversarial inputs are designed to trigger worst cases or common failures.

Adversarial testing is especially important when the algorithm has a performance guarantee. A program that is correct on small examples may still fail by timing out, overflowing, or exhausting memory.

Testing Output with Multiple Correct Answers

When multiple outputs are valid, do not compare against one fixed answer. Write a checker.

Example:

Problem:
  Return any pair of indices i, j such that A[i] + A[j] = target.

Checker:

check_pair(A, target, result):
  if result == none:
    verify no valid pair exists
  else:
    i, j = result
    assert i != j
    assert 0 <= i < n
    assert 0 <= j < n
    assert A[i] + A[j] == target

The checker encodes the acceptance condition from the problem statement.

Common Pitfalls

Do not test only happy paths. Boundary cases often reveal incorrect initialization or termination conditions.

Do not use the optimized algorithm as its own oracle. A test must compare against the specification, a baseline, or an independently checked property.

Do not hard-code one expected output when the problem allows several valid outputs.

Do not ignore performance tests. Correctness on small input does not imply feasibility on maximum input.

Takeaway

Testing turns the specification into executable checks. Use fixed boundary tests, slow baselines, random generation, invariant assertions, and adversarial cases. The goal is not to replace proof, but to catch the mistakes that proofs and informal reasoning often miss.