AlgoScope

Brute Force

algorithmbeginnerTime O(n^2)Space O(1)

Try every candidate. It cannot be wrong, because nothing is skipped, and it cannot be fast, because nothing is skipped. Its cost is the size of the search space, and that number is the baseline every cleverer method has to beat.

80311526311445

Find two values that add up to 10. No sorting, no map, no trick: try every pair once. With 6 values that is 6 x 5 / 2 = 15 pairs at most.

Check your understanding

The player pauses before the one decision in this run and asks what happens next. Here it is, with the answer.

  1. 6 values. How many pairs might brute force check?

    • 6, one per value
    • 15, one per pair
    • 36, n squared

    Answer: 15, one per pair. Each of the 6 values pairs with the 5 others, and each pair is counted twice that way, so 6 x 5 / 2 = 15.

How it runs, step by step

  1. Find two values that add up to 10. No sorting, no map, no trick: try every pair once. With 6 values that is 6 x 5 / 2 = 15 pairs at most.

    Looking for a pair summing to 10 by checking every pair of 6 values.

  2. The search space is every pair (i, j) with i before j. That is the whole cost of brute force: the size of the space, since each candidate is checked in constant time.

    Before searching: how many pairs can there be among 6 values?

  3. Pair (0, 1): 8 + 3 = 11. Not 10. Next pair.

    Checking 8 plus 3, which is 11. No match.

  4. Pair (0, 2): 8 + 15 = 23. Not 10. Next pair.

    Checking 8 plus 15, which is 23. No match.

  5. Pair (0, 3): 8 + 6 = 14. Not 10. Next pair.

    Checking 8 plus 6, which is 14. No match.

  6. Pair (0, 4): 8 + 11 = 19. Not 10. Next pair.

    Checking 8 plus 11, which is 19. No match.

  7. Pair (0, 5): 8 + 4 = 12. Not 10. Next pair.

    Checking 8 plus 4, which is 12. No match.

  8. Pair (1, 2): 3 + 15 = 18. Not 10. Next pair.

    Checking 3 plus 15, which is 18. No match.

  9. Pair (1, 3): 3 + 6 = 9. Not 10. Next pair.

    Checking 3 plus 6, which is 9. No match.

  10. Pair (1, 4): 3 + 11 = 14. Not 10. Next pair.

    Checking 3 plus 11, which is 14. No match.

  11. Pair (1, 5): 3 + 4 = 7. Not 10. Next pair.

    Checking 3 plus 4, which is 7. No match.

  12. Pair (2, 3): 15 + 6 = 21. Not 10. Next pair.

    Checking 15 plus 6, which is 21. No match.

  13. Pair (2, 4): 15 + 11 = 26. Not 10. Next pair.

    Checking 15 plus 11, which is 26. No match.

  14. Pair (2, 5): 15 + 4 = 19. Not 10. Next pair.

    Checking 15 plus 4, which is 19. No match.

  15. Pair (3, 4): 6 + 11 = 17. Not 10. Next pair.

    Checking 6 plus 11, which is 17. No match.

  16. Pair (3, 5): 6 + 4 = 10. That is 10. Found after 14 of 15 checks.

    Checking 6 plus 4, which is 10. That matches the target.

  17. Pair found at indices 3 and 5 after 14 of 15 checks. Brute force is correct because it tries everything, and slow for the same reason: O(n squared) here, where a hash set of seen values would take O(n).

    A pair was found after 14 checks.

Remember

  • Brute force is correct by construction: every candidate is checked.
  • Its cost is the size of the search space. Count the candidates and you have the bound.
  • Write it first, use it to check faster solutions, then beat it.

Topics covered

Related

Where this is used

DatabasesSequential scans in a query planner

PostgreSQL will pick a Seq Scan, reading every row, over an index when the index would not rule out enough rows to pay for itself. Brute force wins there because a full pass is one long sequential read, while an index plan pays a random seek per matching row. Every index plan the planner considers is costed against that scan, so the exhaustive option is the baseline the optimiser actually compares to.

SecurityPassword hashing work factors

An attacker holding a stolen hash file has only brute force available: guess a password, hash it, compare. The total cost is candidates multiplied by cost per candidate, and a defender cannot shrink the candidate space, so bcrypt's cost parameter and Argon2's memory parameter attack the other term. Each step up the work factor doubles both sides, but the attacker pays it across the whole candidate space while the defender pays it once per login, which is why the advice is to raise the cost until a single hash costs about as much latency as a login can absorb.

Text processingCatastrophic backtracking in regex engines

Backtracking engines such as java.util.regex and PCRE match by trying every way the pattern can be divided across the input, which is what lets them support backreferences at all. For a pattern like (a+)+b the candidate count is exponential in the input length, so a few dozen characters can pin a CPU, and that is the ReDoS bug class. RE2 and Go's regexp give up backreferences and simulate an automaton instead, trading expressive power for a search space that stays linear.

CompilersSuperoptimizers

A superoptimizer enumerates every instruction sequence up to a short length cap, tests each against the function it must reproduce, and keeps the shortest one that matches. The length cap is what makes an otherwise absurd search finite, and exhaustiveness is the point: it finds branch-free sequences no hand-written rewrite rule was ever going to propose. Alexia Massalin's 1987 superoptimizer worked this way, using a probabilistic test to throw out most candidates cheaply, and GNU superopt still ships that search for a range of instruction sets. Later tools such as Souper search LLVM IR with an SMT solver instead of enumerating, which gives up the exhaustive guarantee to reach expressions the enumeration could never reach.

Why it works this way

Why j starts at i + 1

Starting j at i would let an element pair with itself, so a target equal to twice any single value reports a false match. Starting j at 0 checks every ordered pair, which does twice the work and finds (j, i) as well as (i, j). Starting at i + 1 visits each unordered pair exactly once, n(n-1)/2 of them, and that count is where the O(n^2) comes from.

Returning early does not change the bound

The return inside the loop helps the average case and does nothing for the worst case: when no pair sums to the target, every candidate is still checked. Timing this on an input where the answer sits in the first few pairs is how people talk themselves into believing brute force is fast enough. Time it on the input with no answer, because that is the case the bound describes.

n^2 is survivable, 2^n is not

Doubling n makes this function four times slower, which is bounded and often fine: ten thousand values is fifty million pairs and finishes in about ten milliseconds, and even a million values is five hundred billion pairs, which is minutes rather than never. Brute force over subsets instead of pairs costs 2^n, where n = 20 is a million candidates and n = 40 is a trillion, so the machine does not get slower, it stops finishing. When the candidate set is exponential the standard first move is meet in the middle: enumerate 2^(n/2) candidates on each half and match them, spending memory to square-root the running time.

Sometimes the brute force is the version you ship

Up to around a hundred elements this loop can beat the O(n) hash-set version on the JVM, because a scan over contiguous memory costs a couple of cycles per pair while every HashSet insert boxes an Int, hashes it, probes and sometimes allocates. Write the same comparison against a flat open-addressed table of primitives and the crossover disappears entirely, so where it sits is a property of the implementation and the machine, not of the analysis. Measure it rather than assume it. The same effect is why standard library sorts drop to insertion sort once a subarray gets small.

Read more

Next up