COMP90038 · Algorithms And Complexity
Brute Force and Exhaustive Search
The honest baseline: solve a problem straight from its definition, with no cleverness, and measure what that costs. The chapter walks the canonical brute-force algorithms — selection sort (repeatedly find the minimum, Θ(n²)), brute-force string matching (slide the pattern, compare, Θ(nm)), and closest pair by checking all pairs (Θ(n²)) — so you can state their bounds cold and recognise them as the things later techniques improve on. It then steps up to exhaustive search (generate-and-test): enumerate every candidate solution and keep the best, the only general attack on the hard combinatorial problems — the travelling salesman (try all permutations, Θ(n!)), the knapsack (try all subsets, Θ(2ⁿ)) and the Hamiltonian circuit. The lesson is not that brute force is good but that it is always available and easy to get right, which makes it the correctness reference and the complexity yardstick for everything that follows.
What this chapter covers
- 01Selection sort — the Θ(n²) min-finding baseline
- 02Brute-force string matching — sliding the pattern, Θ(nm)
- 03Closest pair by checking all pairs — Θ(n²)
- 04Exhaustive search / generate-and-test as the general pattern
- 05TSP (Θ(n!)), knapsack (Θ(2ⁿ)) and Hamiltonian circuits
Worked example: counting the comparisons in selection sort
- +1Comparisons per pass. Pass k scans the suffix of length n − k + 1 and makes n − k comparisons to find its minimum, for k = 1 … n − 1.
- +2Sum them. Total = (n−1) + (n−2) + … + 1 = n(n−1)/2 comparisons — independent of the input order.
- +1Asymptotics. n(n−1)/2 = Θ(n²), and because the count never depends on the data this is the cost in every case (worst = best).
Key terms
- Brute force
- Solving a problem directly from its definition with the most obvious method, accepting a poor running time in exchange for being simple and clearly correct. The reference implementation against which smarter algorithms are checked.
- Selection sort
- Sort by repeatedly selecting the minimum of the unsorted part and swapping it to the front. Always Θ(n²) comparisons but at most n−1 swaps — useful when writes are far more expensive than reads.
- Exhaustive search
- Generate every candidate solution from a combinatorial space and test each, keeping the best. The general (but exponential) attack on optimisation problems with no known efficient algorithm.
- Travelling salesman problem (TSP)
- Find the shortest tour visiting every city exactly once and returning to the start. Brute force tries all (n−1)!/2 permutations — Θ(n!) — making it intractable beyond small n; it is the canonical NP-hard optimisation problem.
- Knapsack (0/1)
- Choose a subset of items, each with a weight and value, to maximise value within a weight budget. Brute force tests all 2ⁿ subsets; the subject later solves it with dynamic programming.
Brute Force and Exhaustive Search FAQ
If brute force is slow, why study it?
Because it is always available, easy to implement and easy to prove correct, so it is the baseline that defines the problem and the yardstick a faster algorithm must beat. Several exam designs ask you to give the brute-force cost first, then improve it — you cannot show the improvement without the baseline.
What is the difference between brute force and exhaustive search?
Brute force solves directly from the definition (e.g. compare all pairs). Exhaustive search is the special case where the candidate space is combinatorial — all permutations, all subsets — and you generate and test every one. Exhaustive search is what makes TSP and knapsack exponential.
When is brute force actually the right choice?
When n is small and guaranteed bounded, when correctness and simplicity matter more than speed, or as a correctness oracle to test a faster algorithm against. For small fixed inputs a Θ(n²) or even Θ(2ⁿ) method can be the pragmatic, bug-free choice.
Exam move
Memorise the brute-force bounds as anchors — selection sort Θ(n²), string match Θ(nm), closest pair Θ(n²), TSP Θ(n!), knapsack Θ(2ⁿ) — because design-and-analyse questions often ask for the naive cost before the improved one, and a wrong baseline drags the whole answer down. Be able to state, for each, exactly which quantity is being counted (comparisons, candidate solutions) and whether the bound is data-dependent. Recognise “try all permutations” and “try all subsets” on sight as the two exponential generate-and-test patterns.
