1.25 Common Failure Modes

Even when the algorithmic idea is correct, implementations fail in predictable ways. These failures are not random. They arise from mismatches between the specification, the model, and the code. Recognizing these patterns early reduces debugging time and prevents subtle errors.

Problem

You have an implementation that behaves incorrectly or inconsistently, and you need a systematic way to identify likely causes.

Solution

Check the implementation against a small set of known failure categories. Most bugs fall into one of these groups.

Boundary Errors

These occur when indices, intervals, or loop limits are incorrect.

Typical cases:

Using left < right instead of left <= right
Forgetting to process the last element
Off-by-one errors in prefix or suffix loops
Mixing inclusive and half-open intervals

Example:

for i = 0 to n:

This accesses A[n], which is outside the array.

Correct:

for i = 0 to n - 1:

Incorrect Invariant

The code updates state in a way that violates the intended invariant.

Typical cases:

Updating state before checking a condition
Forgetting to maintain a relationship between variables
Using stale values after mutation

Example:

best = 0

for maximum subarray sum. This breaks correctness when all values are negative.

Missing Edge Cases

The algorithm works on typical inputs but fails on boundary inputs.

Typical cases:

Empty input not handled
Single-element input misprocessed
Duplicate values ignored
Degenerate graph or tree not handled

Example:

Binary search on an empty array without checking length.

Wrong Data Structure

The algorithm assumes certain operations are cheap, but the implementation uses a structure where they are expensive.

Typical cases:

Using list instead of hash set for membership
Using array where frequent insertions are needed
Using recursion where stack depth is too large

This may not break correctness, but it breaks complexity guarantees.

Hidden Complexity Blowup

The code contains operations whose cost is larger than expected.

Typical cases:

Sorting inside a loop
Copying arrays repeatedly
Using expensive string concatenation
Nested recursion without memoization

Example:

for i = 0 to n - 1:
  sort(A)

This changes time from (O(n \log n)) to (O(n^2 \log n)).

Integer Overflow

Arithmetic exceeds the numeric limits of the chosen type.

Typical cases:

mid = (left + right) // 2
sum exceeds 32-bit range
multiplication overflows before comparison

Example:

Using 32-bit integers for values that may reach (10^{15}).

Floating-Point Errors

Comparisons on approximate values produce incorrect decisions.

Typical cases:

Using x == y for computed floats
Comparing values with accumulated rounding error
Geometry predicates using floating arithmetic without tolerance

State Mutation Bugs

Shared or mutable state is modified incorrectly.

Typical cases:

Reusing arrays across recursive calls
Forgetting to undo changes in backtracking
Modifying a list while iterating over it

Example:

DFS with a global visited set not reset between runs.

Incorrect Termination

Loops or recursion do not terminate or terminate too early.

Typical cases:

Loop condition never becomes false
Recursive call does not reduce problem size
Stopping before processing all candidates

Example:

while left < right:
  left = mid

If mid == left, the loop does not progress.

Wrong Output Contract

The algorithm returns a value that does not match the required output format.

Typical cases:

Returning cost instead of path
Returning index instead of value
Returning 0-based index when 1-based is required
Returning one solution when multiple must be listed

Testing Blind Spots

The algorithm appears correct because tests are insufficient.

Typical cases:

Testing only random inputs
Missing adversarial cases
Using the same flawed logic in baseline and optimized code
Not testing extreme values

Debugging Strategy

When an algorithm fails, use this sequence:

1. Re-check the problem statement and output contract.
2. Test on smallest inputs and edge cases.
3. Print or inspect state at each step.
4. Verify invariants explicitly.
5. Compare with a brute force baseline.
6. Check numeric limits and types.
7. Review loop boundaries and termination.
8. Isolate the smallest failing input.

This process narrows the error quickly.

Failure Pattern Summary

Takeaway

Most algorithmic bugs follow a small set of patterns. By checking boundaries, invariants, data structures, numeric limits, and output contracts systematically, you can diagnose and fix errors without guesswork.