--- title: 'Brute Force and Its Limits' source: 'https://academia.sh/en/courses/advanced-algorithms/brute-force-and-its-limits' course: 'Advanced Algorithms and Problem Solving' language: en updated: '2026-08-17T18:07:24+00:00' license: 'CC BY-SA 4.0' --- # Brute Force and Its Limits Brute force's role in this course is not a slow option but an oracle: exhaustive counting spends 2640 steps on 40 inputs, early-exit pruning gives the same answer in 866 steps, and sampling that looks only at the first six positions diverges from the oracle on 14 inputs in 406 steps. 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. ```python # 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. ```python # 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. ```python 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. ```python # 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. ```python # 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.