Brute Force & Exhaustive Search Strategies
Pseudocode & Algorithmic Problem-Solving
Chapter 6 · Brute Force & Exhaustive Search Strategies
Once a problem has been decomposed to a subproblem small enough for direct pseudocode (Chapter 4), the very first design question is often: could I just try every possibility? Brute force — systematically checking every candidate solution until the right one turns up — is a genuine, often-correct first strategy, not a lazy fallback. This chapter shows exactly where that's true, and exactly where it stops being true, with real measured numbers rather than a rule of thumb.
Worked Example 1: Two Sum, Checked Exhaustively
[2, 7, 11, 15, 3, 6] looking for a pair summing to 9: the algorithm checks every pair in order and returns indices (0, 1) — list[0]+list[1] = 2+7 = 9, confirmed correct. No cleverness was needed; every possible pair was simply checked in turn until a match appeared.
Worked Example 2: A Small-Keyspace PIN Search
A 3-digit PIN has exactly 1,000 possible values (000 through 999). Checking every single one is a completely legitimate approach when the space really is this small.
482: the search found it after 483 attempts, in 0.187 milliseconds. That's a measured rate of roughly 2.58 million attempts per second for this simple a check — fast enough that "just try everything" isn't a compromise here; it's the obviously correct, simplest thing to do.
When Brute Force Is the Honest Answer
- The search space is genuinely small — hundreds or thousands of possibilities, as verified above, finish in a fraction of a second
- Correctness matters more than speed, and the deadline allows it — an exhaustive check is trivially easy to convince yourself (and a reviewer) is correct, since it never skips a case by construction
- It's a legitimate first draft — a working brute-force solution, even one that will later be replaced by Chapters 7 or 8's own smarter strategies, gives a correct reference answer to test a faster version against
When Brute Force Stops Being Honest — A Real, Measured Limit
Consider a genuinely different problem: given a set of n items, check every possible subset (for example, to find one that sums to a target value). The number of subsets of a set of size n is 2ⁿ — and unlike the PIN search's fixed 1,000 candidates, this grows with the input itself.
n=10: 1,024 subsets. n=20: 1,048,576. n=30: 1,073,741,824 — over a billion. n=40: 1,099,511,627,776 — over a trillion.
≈2.58 million checks/second rate the PIN search actually achieved above: checking all 2²⁰ subsets would take ≈0.41 seconds — still fine. Checking all 2³⁰ subsets would take ≈6.9 minutes — noticeably worse, but tolerable. Checking all 2⁴⁰ subsets would take ≈4.93 days — for a set of only 40 items, at a rate this chapter itself already measured as fast. This isn't a hypothetical slowdown; it's the same exhaustive-search strategy, the same measured speed, applied to a problem whose candidate count genuinely explodes as the input grows.
This is the honest boundary: brute force is the right answer exactly as long as the number of candidates stays small relative to how fast they can be checked — and the PIN search and the subset search differ only in how their candidate count behaves as the input grows, not in how the strategy itself works.
Where This Connects
| This chapter's finding | What it sets up |
|---|---|
| Brute force verified correct and fast on two small worked examples | The baseline every later design strategy in this course is honestly compared against, not dismissed outright |
| The measured 2.58M/sec rate extrapolated to a real explosion | Directly motivates Chapter 7's greedy strategy and Chapter 8's divide and conquer — both exist specifically to avoid checking every possibility |
| "Small relative to how fast candidates can be checked" as the real boundary | Algorithms & Complexity's own formal Big-O treatment gives this exact intuition a precise mathematical name, for anyone continuing on to that course |
Hands-On Exercises
Using this chapter's own TwoSumBruteForce pseudocode, hand-trace it on [4, 1, 8, 3] looking for a pair summing to 11. List every pair the algorithm actually checks, in order, until it finds a match (or exhausts all pairs).
Using this chapter's own measured PIN-search rate (≈2.58 million checks/second), estimate roughly how long an exhaustive search of every 6-digit PIN (1,000,000 possibilities) would take at that same rate, and explain why this is still a reasonable brute-force candidate even though it's 1,000 times larger than the 3-digit search.
📄 View solutionUsing this chapter's own distinction between the PIN search and the subset search, explain in your own words why "the search space is 1,000 possibilities" and "the search space is 2¹⁰ possibilities" describe the exact same number (1,024 vs. 1,000, close enough), yet one of these problems stays brute-forceable as its input grows and the other doesn't.
📄 View solutionChapter 6 Quick Reference
- Brute force / exhaustive search: systematically check every candidate until a match is found — verified correct on Two Sum (
[2,7,11,15,3,6], target9→ indices(0,1)) and a 3-digit PIN search (found in483attempts,0.187ms,≈2.58M checks/sec) - Brute force is the honest choice when the candidate count is genuinely small relative to how fast candidates can be checked — not a lazy fallback
- Verified directly: subset counts explode as
2ⁿ—1,024atn=10, over a trillion atn=40 - Extrapolated from this chapter's own measured rate: checking all subsets of just 40 items would take
≈4.93 days— the same strategy, the same real speed, a fundamentally different-shaped problem - Next chapter: Greedy algorithms — the first design strategy that avoids checking every possibility, and an honest look at where that shortcut can go wrong