---

📘 Divide-and-Conquer

(Basic Algorithm Design Technique)

1️⃣ Introduction

Divide-and-Conquer is a fundamental algorithm design technique in which a problem is:

1. Divided into smaller sub-problems
2. Solved recursively
3. Combined to obtain the final solution

This technique is especially effective for problems that can be broken into independent sub-problems of the same type.

---

2️⃣ General Strategy of Divide-and-Conquer

The Divide-and-Conquer approach consists of three main steps:

🔹 1. Divide

Split the problem of size n into smaller sub-problems, usually of size n/2.

🔹 2. Conquer

Solve each sub-problem recursively.
If the sub-problem is small enough, solve it directly (base case).

🔹 3. Combine

Combine the solutions of sub-problems to form the solution of the original problem.

---

3️⃣ Mathematical Representation

The time complexity of divide-and-conquer algorithms is usually expressed using a recurrence relation:

[
T(n) = aT\left(\frac{n}{b}\right) + f(n)
]

Where:

• a = number of sub-problems
• n/b = size of each sub-problem
• f(n) = cost of dividing and combining

---

4️⃣ Example Algorithms Using Divide-and-Conquer

---

🔹 1. Binary Search

Idea:
Divide the sorted array into two halves and search recursively.

Recurrence Relation:
[
T(n) = T(n/2) + O(1)
]

Time Complexity:

• Best Case: O(1)
• Worst Case: O(log n)

---

🔹 2. Merge Sort

Idea:
Divide the array into two halves, sort them recursively, and merge.

Recurrence Relation:
[
T(n) = 2T(n/2) + O(n)
]

Time Complexity:

• Best / Average / Worst Case: O(n log n)

---

🔹 3. Quick Sort

Idea:
Partition the array around a pivot and sort sub-arrays recursively.

Recurrence Relation:

• Best/Average Case:
  [
  T(n) = 2T(n/2) + O(n)
  ]
• Worst Case:
  [
  T(n) = T(n-1) + O(n)
  ]

Time Complexity:

• Best/Average: O(n log n)
• Worst: O(n²)

---

🔹 4. Strassen’s Matrix Multiplication

Recurrence Relation:
[
T(n) = 7T(n/2) + O(n^2)
]

Time Complexity:
[
O(n^{\log_2 7}) \approx O(n^{2.81})
]

---

5️⃣ Advantages of Divide-and-Conquer

• Reduces problem complexity
• Efficient for large input sizes
• Enables parallel processing
• Elegant and structured approach

---

6️⃣ Disadvantages of Divide-and-Conquer

• Recursive overhead
• Higher space usage (stack memory)
• Not suitable for all problems
• Combining step may be costly

---

7️⃣ Comparison with Other Techniques

Technique	Strategy	Example
Divide-and-Conquer	Divide → Solve → Combine	Merge Sort
Greedy	Local optimal choice	Kruskal
Dynamic Programming	Store sub-problem results	Knapsack
Backtracking	Try all possibilities	N-Queen

---

8️⃣ Applications of Divide-and-Conquer

• Searching (Binary Search)
• Sorting (Merge Sort, Quick Sort)
• Matrix multiplication
• Computational geometry
• Large data processing

---

9️⃣ Exam-Oriented Key Points

• Always mention three steps
• Write recurrence relation
• Solve using Master Theorem
• Use examples

---

🔚 Conclusion

Divide-and-Conquer is a powerful and widely used algorithm design technique that simplifies complex problems by breaking them into smaller manageable sub-problems.

Divide-and-Conquer transforms complex problems into simpler ones through recursion.

---