Brute Force and Its Limits

The Algorithms course closed by establishing a measure: operation counting, asymptotic notation, lower bound. In that course the only thing measured was cost, because every algorithm was assumed to be correct. This course opens by removing that assumption.

Choosing a design approach is not merely speeding up; it is accepting a precondition. When the precondition breaks, the approach does not slow down — it gives a wrong answer, and the wrongness cannot be seen from the output, because it still returns a number. This is why brute force stands at the center of the course; but here not as a “slow option,” rather as an oracle. An approach’s number is not the steps it saves but the number of wrong answers it gives once its precondition breaks; an approach whose precondition is not tested against the oracle is considered unmeasured.

• DA1. The measure is steps, not time. No lesson measures wall-clock time.
• DA2. Seed 20260218. The same seed gives the same corpus; every number here is reproducible.
• DA3. The corpus consists of 40 arrays; each array holds 12 values, and the values range from -9 to 20.
• DA4. A step is adding two values and comparing them with the target. The counter counts every step as one.
• DA5. The oracle is always brute force: a procedure that sees every possibility and never exits early. The oracle’s answer is correct by definition.
• DA6. A candidate’s correctness is claimed only by comparison with the oracle. No correctness claim is written without the oracle.
• DA7. A diverging input is one where the oracle and the candidate give different answers; it is counted out of 40.
• DA8. Resolution: 1 divergence out of 40 inputs is considered unmeasured; 3 or more is meaningful.
• DA9. Randomness is modeled with a deterministic generator; the standard library’s random number generator is not used.
• DA10. Every measurement is also run on a second corpus with seed 20260219.

Why Brute Force Can Be an Oracle

Brute force is the procedure that enumerates the entire solution space: every pair, every subset, every ordering. In the text algorithms topic of the Algorithms course, brute-force pattern matching was established as a baseline; the question there was how many comparisons smarter procedures saved over that baseline. Here the role changes.

Brute force’s privilege in this course has nothing to do with speed but with having no precondition. Two pointers requires the array to be sorted, a sliding window requires values to be non-negative, greedy selection requires the local choice to fit the global solution. Exhaustive counting makes no such demand: because it sees every possibility, none of its assumptions can break. The one procedure with no assumption to break is the only procedure that can measure everyone else’s broken assumption.

This cost is paid in every lesson. The oracle is expensive, and its expense is not a flaw but the price of being an oracle. An approach being faster than the oracle is not an achievement; being fast while giving the same answer as the oracle is. What turns this distinction into a number is the count of diverging inputs.

Measurement Framework

Every measurement in the course is done on the same corpus and the same counter. The corpus is built from inputs that deliberately break preconditions; batches that satisfy a precondition are derived from it.

# Measurement framework: corpus and step counter. STEPS are counted, not time.
SEED = 20260218
LENGTH = 12
CORPUS_SIZE = 40


def generator(seed):
    """Deterministic generator. The same seed gives the same corpus."""
    d = seed

    def next_value(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return next_value


def corpus(seed=SEED, n=CORPUS_SIZE, length=LENGTH):
    r = generator(seed)
    items = []
    for i in range(n):
        array = [r(30) - 9 for _ in range(length)]        # -9 .. 20
        items.append({"no": i + 1, "array": array,
                     "negative": any(x < 0 for x in array),
                     "sorted": array == sorted(array)})
    return items


class Counter:
    def __init__(self):
        self.steps = 0

    def add(self, n=1):
        self.steps += n


items = corpus()
print("corpus:", len(items), "arrays x", LENGTH, "values")
print("sorted:", sum(1 for k in items if k["sorted"]),
      "| containing negative:", sum(1 for k in items if k["negative"]))
print("first array:", items[0]["array"])

corpus: 40 arrays x 12 values
sorted: 0 | containing negative: 40
first array: [-8, -5, 2, -1, 2, 5, 4, 1, 16, 17, 6, -1]

Zero of the forty arrays are sorted, forty contain a negative value. This is not an accident but a design choice: the base corpus violates most of the preconditions the course will address. Batches that satisfy a precondition are produced by sorting these arrays or taking their absolute values, so that the two batches come from the same generator and the only difference between them is the precondition itself.

The Oracle’s Step and Two Shortcuts

The measured problem is this: in an array, do two distinct positions exist whose sum equals the target. The target is taken as 11. Three procedures are written. The first is the oracle: it sees every pair and does not stop even after finding a match. The second applies an early exit, stopping at the first match. The third applies sampling, looking only at the first six positions.

# Continuing from the previous block: corpus, Counter and items come from there.
TARGET = 11


def oracle_full(array, target, s):
    """Sees every pair, never exits early. This is the oracle."""
    found = False
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.add()
            if array[i] + array[j] == target:
                found = True
    return found


def early_exit(array, target, s):
    """EARLY EXIT: stops at the first match. Skipped pairs cannot change the answer."""
    for i in range(len(array)):
        for j in range(i + 1, len(array)):
            s.add()
            if array[i] + array[j] == target:
                return True
    return False


def sampled(array, target, s, look=6):
    """SAMPLING: looks only at the first 'look' positions. An unseen pair is unknown."""
    for i in range(min(look, len(array))):
        for j in range(i + 1, min(look, len(array))):
            s.add()
            if array[i] + array[j] == target:
                return True
    return False


def measure(candidate, oracle, items, target):
    """Compares the candidate with the oracle; counts diverging inputs."""
    diverging, candidate_total, oracle_total = [], 0, 0
    for k in items:
        s1, s2 = Counter(), Counter()
        if candidate(k["array"], target, s1) != oracle(k["array"], target, s2):
            diverging.append(k["no"])
        candidate_total += s1.steps
        oracle_total += s2.steps
    return {"input": len(items), "diverging": len(diverging), "diverging_no": diverging[:6],
            "candidate_steps": candidate_total, "oracle_steps": oracle_total,
            "ratio": round(oracle_total / candidate_total, 2) if candidate_total else 0.0}


s = Counter()
for k in items:
    oracle_full(k["array"], TARGET, s)
print("oracle (exhaustive count) total steps:", s.steps)
print("early exit", measure(early_exit, oracle_full, items, TARGET))
print("sampling  ", measure(sampled, oracle_full, items, TARGET))

oracle (exhaustive count) total steps: 2640
early exit {'input': 40, 'diverging': 0, 'diverging_no': [], 'candidate_steps': 866, 'oracle_steps': 2640, 'ratio': 3.05}
sampling   {'input': 40, 'diverging': 14, 'diverging_no': [1, 2, 3, 4, 8, 9], 'candidate_steps': 406, 'oracle_steps': 2640, 'ratio': 6.5}

Three numbers stand side by side. The oracle spends 2640 steps on 40 inputs; this is exactly 66 pairs per array and does not change with the input. Early exit spends 866 steps — 3.05 times less than the oracle — and diverges from the oracle on none of the 40 inputs. Sampling spends 406 steps — 6.50 times less than the oracle — and diverges from the oracle on 14 of the 40 inputs. The diverging-input ratio is 0.3500, far above the resolution.

The lesson carried by these three rows is the frame for the rest of the course. There are two kinds of shortcuts, and the two cannot be told apart from the output alone. Early exit preserves correctness because it knows the pairs it skips cannot change the answer: once a match is already found, the remaining pairs cannot turn the answer away from True. Sampling does not rest on such knowledge; it has no guarantee about the pairs it never sees, and it genuinely errs on 14 inputs.

The numbers of the diverging inputs also carry a pattern. The first six in the output are 1, 2, 3, 4, 8, and 9; what they share is that for every pair that hits the target, at least one end falls outside the first six positions. Sampling never sees those pairs and answers “no”. The cause of the error is not a computational mistake but an assumption about an unseen region; this is the shared shape of every approach’s error in this course.

The order of the numbers is also meaningful. The wrong one is faster than the correct one: sampling takes 406 steps, early exit 866. If speedup is measured alone, sampling wins. The moment diverging inputs are added to the measure, the ranking reverses. This is the first form of the course’s second claim: speeding up moves you closer to being wrong, and being wrong is attractive because it is cheap.

The Limit of Exhaustive Search

The question of when brute force is acceptable is answered with a step budget: the number of steps allowed in a run is fixed, and for each search family, the input size that fits within that budget is computed. The budget here is taken as one hundred million steps.

from math import comb, factorial

BUDGET = 10**8          # upper limit of steps allowed in one run


def fitting_n(count_fn, limit=20000):
    """The largest n that fits within the step budget."""
    best = 0
    for n in range(1, limit + 1):
        if count_fn(n) > BUDGET:
            break
        best = n
    return best


FAMILIES = (("pair selection", lambda n: comb(n, 2)),
            ("triple selection", lambda n: comb(n, 3)),
            ("subsets", lambda n: 2 ** n),
            ("permutations", factorial))

print("exhaustive search family   n=12 steps          n=20 steps  n fitting budget")
for name, f in FAMILIES:
    print(f"  {name:16s} {f(12):10d} {f(20):19d} {fitting_n(f):15d}")
print("step budget:", BUDGET)

exhaustive search family   n=12 steps          n=20 steps  n fitting budget
  pair selection           66                 190           14142
  triple selection        220                1140             844
  subsets                4096             1048576              26
  permutations      479001600 2432902008176640000              11
step budget: 100000000

Four families correspond to four separate worlds under the same budget. Pair selection tolerates an input above fourteen thousand; triple selection stops at 844; the search that counts every subset stops at 26, the one that counts every permutation at 11. The gap between them is why this course teaches not just speedup but approach selection: a solution left in the permutation family blows its budget again the moment the input grows by one element.

It should be noted that this bound does not remove the oracle’s role. Even if a procedure will be called in production with n=1000, comparison against the oracle is done on a corpus with n=12; there, exhaustive counting is 2640 steps and strains no budget. Brute force ends at small inputs as a solution, but stays usable in every lesson as a measurement tool.

The Corpus Size Is the Oracle’s Budget

The previous table also explains why the corpus is built from twelve-element arrays. Throughout the course, the oracle will not stay confined to the pair-selection family; some problems will require scanning every subset. That scan depends directly on the corpus’s element count.

# Continuing from the previous blocks: corpus, Counter and LENGTH come from there.
LIMIT = 30


def oracle_subset(array, limit, s):
    """The largest subset sum not exceeding the limit. Every subset is scanned."""
    best = 0
    for mask in range(1 << len(array)):
        s.add()
        total = sum(array[i] for i in range(len(array)) if mask >> i & 1)
        if total <= limit and total > best:
            best = total
    return best


items = corpus()
s = Counter()
for k in items:
    oracle_subset(k["array"], LIMIT, s)
print("subsets per array:", 2 ** LENGTH, "| oracle steps on 40 arrays:", s.steps)
for length in (12, 16, 20, 26):
    print(f"  length {length:2d} -> 40 arrays {40 * 2 ** length:12d} steps",
          "(within budget)" if 40 * 2 ** length <= 10**8 else "(outside budget)")

subsets per array: 4096 | oracle steps on 40 arrays: 163840
  length 12 -> 40 arrays       163840 steps (within budget)
  length 16 -> 40 arrays      2621440 steps (within budget)
  length 20 -> 40 arrays     41943040 steps (within budget)
  length 26 -> 40 arrays   2684354560 steps (outside budget)

A twelve-element array has 4096 subsets; on forty arrays the oracle spends 163,840 steps, using two-thousandths of the budget. The same oracle rises to 41,943,040 steps on twenty-element arrays — it still fits, but eats forty percent of the budget. At twenty-six elements, the corpus itself exceeds the budget by twenty-seven times.

The rule that follows is the foundation of the course’s measurement scheme: the corpus’s element count is chosen relative to the most expensive oracle to be measured. Twelve is the largest comfortable number that still carries even a subset scan on a corpus of forty inputs. Growing the corpus does not give richer input; it only makes the oracle unreachable and removes the measurement. Just as there is a limit to speeding up an approach, there is a limit to testing it, and both are paid from the same budget.

The Second Corpus

Whether the ratio measured on a single corpus depends on that corpus is tested separately.

# Continuing from the previous blocks: corpus, measure and the three procedures come from there.
for label, seed in (("first corpus (20260218)", 20260218),
                    ("second corpus (20260219)", 20260219)):
    items = corpus(seed)
    e = measure(early_exit, oracle_full, items, TARGET)
    o = measure(sampled, oracle_full, items, TARGET)
    print(label)
    print("  early exit: diverging", e["diverging"], "/ 40 | ratio",
          round(e["diverging"] / 40, 4), "| candidate steps", e["candidate_steps"])
    print("  sampling  : diverging", o["diverging"], "/ 40 | ratio",
          round(o["diverging"] / 40, 4), "| candidate steps", o["candidate_steps"])

first corpus (20260218)
  early exit: diverging 0 / 40 | ratio 0.0 | candidate steps 866
  sampling  : diverging 14 / 40 | ratio 0.35 | candidate steps 406
second corpus (20260219)
  early exit: diverging 0 / 40 | ratio 0.0 | candidate steps 970
  sampling  : diverging 21 / 40 | ratio 0.525 | candidate steps 512

Early exit’s diverging count is zero in both corpora; this is the expected result, because early exit’s correctness rests not on the input but on the observation that skipped branches cannot change the answer. Sampling’s ratio rises from 0.3500 to 0.5250. The two ratios are of the same order of magnitude — both between a third and a half of the inputs — but the difference between them is far above the resolution. The reading is this: there are inputs where sampling is wrong, and they are countable; how many inputs it is wrong on depends on the corpus and cannot be reported with a single number.

Summary

• In this course, brute force is not a slow option but an oracle; its privilege comes not from speed but from having no precondition to break.
• On the same problem, the oracle spends 2640 steps on 40 inputs, early exit 866 steps (3.05 times less, 0 diverging inputs), sampling 406 steps (6.50 times less, 14 diverging inputs).
• The two kinds of shortcut cannot be told apart from the output: early exit knows the branches it skips cannot change the answer, sampling does not.
• The wrong one is faster than the correct one; until diverging inputs are added to the measure, sampling looks like the winner.
• With a hundred-million-step budget, pair selection fits up to 14,142 elements, triple selection up to 844, subset search up to 26, permutation search up to 11; the oracle’s role is unaffected by this bound because measurement is done on a 12-element corpus.
• On the second corpus, early exit’s diverging count is still 0, sampling’s is 21 instead of 14; the ratio stays the same order of magnitude, but its exact value depends on the corpus.

Next Step

In this lesson, brute force ran undivided, as a single piece. The first design approach splits the problem: it reduces the same problem to two smaller copies of itself, solves each one, and combines the results. The next lesson establishes this approach’s recurrence and counts two questions — on how many inputs a wrong answer appears when the combine step is left incomplete, and where the input size ends at which splitting saves no steps.