Brute Force Method of Algorithm Design

Definition

Brute force (exhaustive search) tries all possible candidates and picks those satisfying constraints. Simplest paradigm, directly from problem statement, no clever pruning.

Characteristics

• Generates entire solution space, tests each candidate.
• Always correct (finds optimum if enumerates all), but often exponential $O(n!)$, $O(2^n)$, $O(n^n)$.
• Serves as baseline to compare smarter algorithms and for small $n$ verification.

Steps

1. Enumerate all candidates (e.g., permutations, subsets, partitions).
2. Test feasibility (constraints) and evaluate objective.
3. Keep best feasible.

Examples

1. Sorting by brute force: Generate all $n!$ permutations, test if sorted → $Θ(n·n!)$ vs $Θ(n\log n)$ optimal.

2. TSP brute force: Enumerate $(n-1)!/2$ tours, compute length, pick min → $O(n!)$ vs DP Held-Karp $O(n^2 2^n)$.

3. Selection / Search: Linear search $O(n)$ brute vs binary $O(\log n)$ (needs sortedness).

4. String Matching brute force: For text $T[0..n-1]$, pattern $P[0..m-1]$, slide window: for $i=0..n-m$ compare $P[0..m-1]$ with $T[i..i+m-1]$ → worst $O((n-m+1)m)=O(nm)$ vs KMP $O(n+m)$.

BruteForceMatch(T,P):
  for i=0..n-m:
    j=0; while j<m and P[j]==T[i+j]: j++
    if j==m: return i
  return -1

5. Closest Pair brute: Check all $\binom{n}{2}$ pairs → $O(n^2)$ vs divide&conquer $O(n\log n)$.

Advantages / Disadvantages

• Pros: Simple, easy to implement/correct, covers all cases, good for small $n$ or to prove optimality via exhaustion.
• Cons: Infeasible for large $n$; does not exploit structure; usually improved by divide&conquer, DP, greedy, or heuristics.

Often first attempt; then optimize with clever design.