PGDDSA Study · Semester 1

PGD01C02

Module 5 · Data Structures and Algorithm Design

Brute Force Approach

Core Titles

Key headlines and terms for quick recall

Brute Force — try every possible solution
Simple to implement, often slow ( $O(2^n)$ , $O(n!)$ )
Use cases — small inputs, baseline, problem definition
Examples: linear search, naive string matching, subset enumeration, TSP, password cracking
Pros: simple, always correct
Cons: doesn't scale
Often refined by other techniques (divide-and-conquer, dp)

Basic Idea

What it is, why it matters, how it works

What is Brute Force?

Brute Force is the most direct problem-solving approach: try all possible candidates until you find the answer. It is often the first algorithm one writes, before optimising.

Characteristics

Conceptually simple.
Easy to implement and verify.
Almost always correct.
Almost always slow on large inputs.

Classic brute-force algorithms

1. Linear search.

def linear_search(arr, x):
    for i, val in enumerate(arr):
        if val == x:
            return i
    return -1

Time: $O(n)$ . Brute because we try every element — no use of sorting or hashing.

2. Naive string matching.

def naive_match(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):
        if text[i:i+m] == pattern:
            return i
    return -1

Time: $O(nm)$ . KMP and Boyer-Moore improve to $O(n + m)$ .

3. Bubble Sort.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Time: $O(n^2)$ . Brute because we compare every pair repeatedly.

4. Subset enumeration.

Generate all $2^n$ subsets of a set to find one with desired property. $O(2^n)$ .

5. Travelling Salesman Problem (TSP) by brute force.

Try every permutation of $n$ cities; compute tour length; keep the minimum. $O(n!)$ — only feasible up to $n \approx 10$ .

6. Password cracking.

Try every combination of characters. Exponential. Defeated by hashing + slow KDFs (bcrypt, Argon2).

When brute force is OK

Small $n$ . A $O(n^2)$ algorithm on $n = 50$ is instant.
Baseline. To validate a smarter algorithm's output.
Problem definition. Sometimes you don't yet know how to optimise; brute force gets a working answer.
Easily parallelisable. Brute-force search can spread across cores / GPUs.

When it fails

$n \ge$ ~30 with $O(2^n)$ , ~12 with $O(n!)$ — combinatorial explosion.

Refinements over brute force

Divide and Conquer — reduce by halving.
Greedy — commit to the best-looking choice; skip alternatives.
Dynamic Programming — store sub-solutions to avoid recomputation.
Branch and Bound — prune sub-trees that cannot improve current best.
Heuristics / metaheuristics — simulated annealing, genetic algorithms, ant colony for NP-hard.

Cryptographic example

RSA encryption is secure precisely because brute-force factoring of large primes is $O(\sqrt{n})$ with the best known algorithms — astronomical for 2048-bit keys.

Why study it

Sets a baseline complexity to beat.
Teaches you the search space of the problem.
Often the simplest correct version is a useful test oracle.

Important caveat

Brute force is correct but rarely efficient. Production systems demand smarter algorithms — but understanding the brute-force version is the first step.

Mind Map

Visual structure of the concept

BRUTE FORCE
├── Try every possibility
├── Pros: simple, correct
├── Cons: exponential / factorial growth
├── Examples
│   ├── Linear search  O(n)
│   ├── Naive string match  O(nm)
│   ├── Bubble sort  O(n²)
│   ├── Subset enumeration  O(2ⁿ)
│   └── TSP brute force  O(n!)
└── Refined by
    ├── Divide & Conquer
    ├── Greedy
    ├── Dynamic Programming
    ├── Branch & Bound
    └── Heuristics

Exam Q&A

Part A (2 marks) and Part B (20 marks) style questions

Part A (2 marks each)

Q1. Define the Brute Force algorithmic technique. A direct problem-solving approach that examines every possible candidate solution until one satisfying the problem is found. Simple, almost always correct, but often slow on large inputs.

Q2. Give two examples of brute-force algorithms.

Linear search — scan every element until the target is found, $O(n)$ .
Naive string matching — slide pattern over text and compare at each position, $O(nm)$ .

Q3. What are the limitations of brute force? It does not scale — typical brute-force runtimes are $O(n^2)$ , $O(2^n)$ or $O(n!)$ , making them infeasible beyond small $n$ . It is used as a baseline or for small inputs and is refined by smarter techniques (DP, divide-and-conquer, greedy, branch-and-bound).

Part B (20 marks)

Q. Explain the Brute Force algorithm-design technique. Discuss its strengths, weaknesses and applications with examples. How is it refined by other algorithmic paradigms?

Definition.

Brute Force tries every possible candidate solution and picks the one that works (or the best one). It is the most direct problem-solving paradigm — straightforward to code, easy to verify, and almost always slow on large inputs.

Characteristics.

Iterates through the entire candidate space.
Requires no clever insight — useful as a baseline.
Almost always correct (no missed cases).
Time complexity often exponential or factorial.

Examples.

1. Linear search.

for i = 1 to n:
    if A[i] == x: return i
return -1

$O(n)$ . Simple but loses to binary search $O(\log n)$ on sorted data.

2. Bubble Sort.

for i = 1 to n:
    for j = 1 to n − i:
        if A[j] > A[j+1]: swap

$O(n^2)$ . Refined by merge sort $O(n \log n)$ .

3. Naive string matching. For each text position, compare the pattern character-by-character. $O(nm)$ . KMP / Boyer-Moore reduce to $O(n + m)$ .

4. Subset-sum. Enumerate all $2^n$ subsets and check which sum to target. $O(2^n)$ . Refined by Dynamic Programming to $O(n \cdot T)$ .

5. Travelling Salesman Problem. Try all $n!$ permutations. Refined by:

Dynamic Programming (Held–Karp) → $O(n^2 2^n)$ .
Branch and Bound, Christofides ( $\le 1.5 \cdot$ OPT).

6. Password cracking. Try every combination of characters. Exponential. Defended by slow hash functions (bcrypt, Argon2).

Strengths.

Simple to implement.
Always correct (when search space is finite).
Trivially parallelisable — different cores try different candidates.
Provides a baseline for benchmarking optimised algorithms.

Weaknesses.

Exponential / factorial scaling — infeasible for $n >$ ~30 or 12.
Wastes work re-exploring already-explored sub-problems.
Inelegant — gives no insight into the problem's structure.

When brute force is acceptable.

Small input size.
Pre-computation / one-off tasks.
As an oracle to validate smarter algorithms.
When clarity matters more than speed.

Refinements by other paradigms.

Refinement	Technique	Example
Halve at each step	Divide-and-Conquer	Merge sort, binary search
Make best local choice	Greedy	Kruskal's MST, Huffman coding
Cache sub-solutions	Dynamic Programming	LCS, knapsack
Prune impossible branches	Branch and Bound	TSP, 0/1 knapsack
Approximate good-enough	Heuristics / Metaheuristics	Simulated annealing, GA
Randomised tries	Monte Carlo / Las Vegas	Randomised quicksort

Take-away. Brute force is the honest baseline. Knowing the brute-force solution is a prerequisite for designing a smarter one. Production systems almost always replace brute force with structured search — but the brute-force reference helps prove correctness and bound speed-ups.

Algorithm Analysis: Time and Space Complexity Divide and Conquer