1.12 Brute Force Baselines

A brute force baseline is the simplest correct algorithm you can write from the problem statement. It may be too slow for the final constraints, but it is valuable because it gives you a reference answer, exposes edge cases, and clarifies what the optimized algorithm must preserve.

A good baseline is intentionally direct. It should follow the definition of the problem more closely than the efficient solution does. This makes it easier to inspect, easier to trust, and easier to use as a testing oracle.

Problem

You need a simple implementation that produces correct answers for small inputs, so that you can test and validate a faster algorithm.

Solution

Write the baseline by enumerating all candidates and selecting the one that satisfies the specification.

Use this pattern:

best = initial value

for each candidate solution:
  if candidate is valid:
    update best according to objective

return best

For decision problems, return as soon as a valid witness is found:

for each candidate:
  if candidate satisfies condition:
    return true

return false

Example: Two Sum

Problem:

Given an array A and a target value t, decide whether there are two distinct indices i and j such that A[i] + A[j] = t.

A brute force solution checks every pair:

two_sum_slow(A, t):
  n = length(A)

  for i = 0 to n - 1:
    for j = i + 1 to n - 1:
      if A[i] + A[j] == t:
        return true

  return false

The algorithm is correct because every valid pair appears exactly once in the nested loops. If a pair exists, the algorithm finds it. If the loops finish, no pair exists.

The time complexity is (O(n^2)). The auxiliary space is (O(1)).

Example: Maximum Subarray Sum

Problem:

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

The brute force solution enumerates every subarray:

max_subarray_slow(A):
  n = length(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

This follows the definition directly. A subarray is determined by its left and right endpoints, and the loops visit every pair with left <= right.

The time complexity is (O(n^2)), since there are (n(n+1)/2) subarrays. The auxiliary space is (O(1)).

Example: Shortest Path by Exhaustive Search

For graph problems, brute force may be expensive, but it can still be useful on tiny inputs.

Problem:

Given a weighted graph, find the minimum cost simple path from s to t.

A brute force baseline can enumerate all simple paths from s to t, compute their costs, and return the minimum.

shortest_path_slow(G, s, t):
  best = infinity

  dfs(v, visited, cost):
    if v == t:
      best = min(best, cost)
      return

    for each edge (v, u, w):
      if u not in visited:
        add u to visited
        dfs(u, visited, cost + w)
        remove u from visited

  dfs(s, {s}, 0)
  return best

This is not suitable for large graphs because the number of simple paths can be exponential. As a baseline, however, it is useful for testing Dijkstra, Bellman-Ford, or dynamic programming on small graphs.

Why Baselines Matter

A brute force baseline gives you several practical benefits.

It provides an oracle for random testing. You can generate many small inputs and compare the optimized algorithm against the baseline.

It clarifies the specification. If the baseline is hard to write, the problem statement may still be ambiguous.

It reveals edge cases. Since the baseline follows the definition directly, it often handles cases that an optimized algorithm accidentally excludes.

It helps debug. When the fast algorithm disagrees with the baseline, the input becomes a concrete counterexample.

Baseline vs Optimized Algorithm

Correctness Argument

For brute force algorithms, correctness usually follows from exhaustive enumeration.

A typical proof has two parts:

Coverage:
  Every candidate allowed by the specification is examined.

Selection:
  The algorithm returns the best valid candidate according to the objective.

For decision problems:

Soundness:
  If the algorithm returns true, it found a valid witness.

Completeness:
  If a valid witness exists, enumeration eventually reaches it.

This proof style is simple and robust.

Common Pitfalls

Do not optimize the baseline too early. The point is clarity. If the baseline becomes clever, it becomes harder to trust.

Do not run the baseline on large inputs. It exists for validation, not production.

Do not use the same flawed helper logic in both baseline and optimized versions. Shared bugs can make both algorithms agree incorrectly.

Do not skip invalid or boundary candidates unless the specification says they are invalid. Exhaustive enumeration should match the problem exactly.

Takeaway

A brute force baseline is a reference implementation derived directly from the specification. It is often too slow for production, but it is one of the strongest tools for testing, debugging, and validating optimized algorithms.