---

📘 Brute Force Algorithm (Naive Method)

The Brute Force algorithm is the simplest method for solving a problem:
👉 It tries all possible solutions until it finds the correct one.

In other words:

A brute force algorithm systematically checks every possible candidate until a solution is found.

It does not use heuristics, patterns, or optimization — it relies on pure exhaustive search.

---

📌 Key Characteristics

• Simple and straightforward
• Guaranteed to find a solution (if one exists)
• Inefficient for large inputs
• Often used as a baseline for comparison with optimized algorithms

---

📘 Brute Force in Different Problems

✔ 1. Searching

Linear Search is a brute force method:

• Compare the target with every element in the list
• Time: O(n)

---

✔ 2. String Matching

Naive String Matching:

• Try to match pattern at every position in text
• Time: O(n × m)

---

✔ 3. Optimization Problems

Examples:

• Traveling Salesman Problem (TSP): Try all permutations
  • Time: O(n!)
• Subset sum: Try all subsets
  • Time: O(2ⁿ)

---

✔ 4. Password Cracking (real-world example)

• Try every possible string until password matches
• Very slow for long passwords
• But guaranteed to find the result

---

📌 Why Study Brute Force?

Even though brute force is inefficient, it is important because:

1. Easy to implement
2. Used to validate optimized solutions
3. Often used when input size is small
4. Sometimes only feasible solution when no better algorithm exists
5. Helps understand the problem before designing improvements

---

📘 Brute Force Algorithm – General Structure

for each candidate solution:
    if candidate satisfies problem conditions:
        return candidate

---

📌 Time & Space Complexity

• Time complexity: Usually very high → exponential or factorial
  • O(n), O(n²), O(2ⁿ), O(n!), etc.
• Space complexity: Usually low, often O(1) or O(n)

---

📘 Advantages of Brute Force

• ✔ Simple to write and understand
• ✔ Guarantees to find solution (if it exists)
• ✔ No special knowledge required
• ✔ Works well for small-sized problems
• ✔ Useful for test-case generation and correctness checking

---

📘 Disadvantages of Brute Force

• ❌ Very slow for large inputs
• ❌ May perform unnecessary work
• ❌ Not practical for real-time or large-scale systems
• ❌ Often leads to exponential running time

---

📘 Brute Force Example in Python (Linear Search)

def brute_force_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1


# Example usage
arr = [7, 3, 9, 1, 5]
print(brute_force_search(arr, 1))  # Output: 3

---

📘 Brute Force Example (String Matching) in Python

def brute_force_string_match(text, pattern):
    n, m = len(text), len(pattern)
    positions = []

    for i in range(n - m + 1):
        match = True
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            positions.append(i)

    return positions


print(brute_force_string_match("ABAAABCD", "ABC"))  # Output: [4]

---

📘 Summary (Exam Notes)

• Brute Force = try all possibilities
• Simple but inefficient
• Used in:
  • Linear Search
  • Naive String Matching
  • TSP
  • Subset Problems
• Time complexity often exponential
• Great for small input sizes or baseline comparison
• Easy to implement and guarantees correctness

---