Divide and Conquer
Divide and Conquer is an important algorithmic technique where we solve a big problem by breaking it into smaller problems, solving those smaller problems, and then combining their results.
It is closely connected to recursion.
1. What is Divide and Conquer?
The basic idea is:
Big Problem ↓ Divide ↓ Smaller Problems ↓ Conquer ↓ Solve Smaller Problems ↓ Combine ↓ Final Answer
There are three main steps:
1. Divide
Break the problem into smaller subproblems.
2. Conquer
Solve each smaller subproblem, usually using recursion.
3. Combine
Combine the solutions of the smaller problems to get the final answer.
2. Simple Real-Life Example
Suppose you have 1000 books and want to find a particular book.
Instead of checking all 1000 one by one:
1000 books ↓ Divide into 500 + 500 ↓ Choose the half where the book can be ↓ 500 ↓ 250 + 250 ↓ 125 + 125 ↓ ... ↓ 1 book
This idea is used by Binary Search.
3. Divide and Conquer Structure
A general recursive structure looks like:
solve(problem) { if (problem is small) { return direct_answer; } divide problem; solve(left_problem); solve(right_problem); combine results; }
The important thing is that the function keeps calling itself on smaller inputs.
4. Example: Binary Search
Binary Search is one of the simplest examples of Divide and Conquer.
Suppose:
[10, 20, 30, 40, 50, 60, 70]
We want to find 60.
First check the middle:
[10, 20, 30, 40, 50, 60, 70] ↑ 40
60 > 40, so we don't need the left half.
[50, 60, 70]
Again:
[50, 60, 70] ↑ 60
Found!
C++ Code
#include <iostream> #include <vector> using namespace std; int binarySearch(vector<int>& arr, int left, int right, int target) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (target < arr[mid]) return binarySearch(arr, left, mid - 1, target); return binarySearch(arr, mid + 1, right, target); } int main() { vector<int> arr = {10, 20, 30, 40, 50, 60, 70}; int index = binarySearch(arr, 0, arr.size() - 1, 60); cout << index; return 0; }
Complexity
Each step cuts the problem approximately in half:
n n/2 n/4 n/8 n/16 ... 1
Therefore:
Time: O(log n)
Recursive space: O(log n)
5. Merge Sort
Merge Sort is one of the most important Divide and Conquer algorithms.
It follows all three steps clearly:
Divide Conquer Combine
Suppose:
[38, 27, 43, 3, 9, 82, 10]
Step 1 — Divide
[38 27 43 3 9 82 10] / \ [38 27 43] [3 9 82 10] / \ / \ [38] [27 43] [3 9] [82 10]
Keep dividing until each part has one element.
[38] [27] [43] [3] [9] [82] [10]
6. Conquer
Now recursively solve the smaller arrays.
For example:
[27] + [43] ↓ [27, 43]
And:
[38] + [27,43] ↓ [27,38,43]
7. Combine
Finally, merge the sorted parts.
[27, 38, 43] [3, 9, 10, 82] \ / \ / \ / [3, 9, 10, 27, 38, 43, 82]
8. Merge Sort C++ Implementation
#include <iostream> #include <vector> using namespace std; void merge(vector<int>& arr, int left, int mid, int right) { vector<int> temp; int i = left; int j = mid + 1; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp.push_back(arr[i]); i++; } else { temp.push_back(arr[j]); j++; } } while (i <= mid) { temp.push_back(arr[i]); i++; } while (j <= right) { temp.push_back(arr[j]); j++; } for (int k = 0; k < temp.size(); k++) { arr[left + k] = temp[k]; } } void mergeSort(vector<int>& arr, int left, int right) { if (left >= right) return; int mid = left + (right - left) / 2; // Divide mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); // Combine merge(arr, left, mid, right); } int main() { vector<int> arr = {38, 27, 43, 3, 9, 82, 10}; mergeSort(arr, 0, arr.size() - 1); for (int x : arr) { cout << x << " "; } return 0; }
Output:
3 9 10 27 38 43 82
9. Why is Merge Sort O(n log n)?
At each level, the array is divided into smaller parts.
Level 0: n ↓ Level 1: n/2 + n/2 ↓ Level 2: n/4 + n/4 + n/4 + n/4 ↓ ...
The number of levels is:
log₂(n)
At every level, merging all elements requires:
O(n)
Therefore:
O(n) × O(log n) ↓ O(n log n)
So:
Best: O(n log n)
Average: O(n log n)
Worst: O(n log n)
Extra Space: O(n)
10. Quick Sort
Quick Sort is another famous Divide and Conquer algorithm.
Instead of splitting exactly in half, it chooses a pivot.
Example:
[8, 3, 1, 7, 0, 10, 2]
Suppose pivot = 7.
Partition:
Smaller than 7 Pivot Greater than 7 [3,1,0,2] 7 [8,10]
Then recursively sort both sides:
[3,1,0,2] 7 [8,10] ↓ ↓ [0,1,2,3] 7 [8,10]
Final:
[0,1,2,3,7,8,10]
Quick Sort therefore follows:
Choose Pivot ↓ Partition ↓ Sort Left ↓ Sort Right
Average complexity:
O(n log n)
Worst case:
O(n²)
The worst case can happen when pivot selection repeatedly creates very unbalanced partitions.
11. Divide and Conquer Recurrence
This is an important concept for DSA.
For Merge Sort:
T(n) = 2T(n/2) + O(n)
Why?
There are:
2 smaller problems
Each has size:
n/2
And merging takes:
O(n)
Therefore:
T(n) = 2T(n/2) + O(n)
Result:
T(n) = O(n log n)
12. Binary Search Recurrence
Binary Search has only one smaller problem:
T(n) = T(n/2) + O(1)
Therefore:
T(n) = O(log n)
13. Common Divide and Conquer Algorithms
Some important examples are:
| Algorithm | Complexity |
|---|---|
| Binary Search | O(log n) |
| Merge Sort | O(n log n) |
| Quick Sort | O(n log n) average |
| Maximum Subarray | O(n log n) divide-and-conquer approach |
| Closest Pair of Points | O(n log n) |
| Strassen Matrix Multiplication | ~O(n².81) |
| Fast Exponentiation | O(log n) |
14. Divide and Conquer vs Recursion
They are related but not the same thing.
Recursion
A function calls itself.
function ↓ function ↓ function
Divide and Conquer
A problem is divided into smaller problems and solved recursively.
Problem / \ Problem Problem / \ / \ ... ... ... ...
So:
Divide and Conquer commonly uses recursion, but recursion itself does not necessarily mean Divide and Conquer.
For example, factorial is recursive:
factorial(n) ↓ factorial(n-1) ↓ factorial(n-2)
But it isn't really a Divide and Conquer algorithm because it doesn't divide the problem into multiple independent subproblems.
15. Divide and Conquer vs Greedy
You just studied Greedy, so this difference is important.
| Feature | Divide & Conquer | Greedy |
|---|---|---|
| Main idea | Break problem | Make best current choice |
| Uses recursion | Usually | Not necessarily |
| Solves subproblems | Yes | Usually no |
| Reconsiders choices | Not the main idea | No |
| Example | Merge Sort | Activity Selection |
| Example | Binary Search | Fractional Knapsack |
| Example | Quick Sort | Dijkstra |
Mental model
Divide and Conquer:
Big problem ↓ Break it ↓ Solve smaller problems ↓ Combine
Greedy:
Problem ↓ Best choice now ↓ Commit ↓ Best choice now ↓ Commit
16. Divide and Conquer vs Dynamic Programming
This is also important because Dynamic Programming comes later in your roadmap.
Divide and Conquer
Usually solves independent subproblems.
Problem / \ A B
A and B don't significantly overlap.
Dynamic Programming
Often has overlapping subproblems.
Problem / \ A B \ / C
The same subproblem may be needed multiple times.
DP stores previous results to avoid repeated work.
17. Advantages
1. Efficient algorithms
Many efficient algorithms use Divide and Conquer.
For example:
Binary Search → O(log n) Merge Sort → O(n log n)
2. Easier problem decomposition
A large problem becomes smaller and easier to understand.
3. Naturally works with recursion
The recursive structure often matches the problem structure.
4. Can support parallel processing
Independent subproblems can sometimes be processed simultaneously.
18. Disadvantages
1. Recursion overhead
Recursive calls require stack memory.
2. Extra memory
Some algorithms such as Merge Sort require additional memory.
3. Combining can be expensive
The divide step may be easy, but combining results can require significant work.
4. Not every problem fits
Some problems are better solved using:
- Greedy
- Dynamic Programming
- Backtracking
- Hashing
- Graph algorithms
19. How to Identify Divide and Conquer
When solving a problem, ask:
Can I divide the problem? ↓ Can I solve each smaller part independently? ↓ Can I combine their answers? ↓ YES ↓ Divide and Conquer may work
Look for phrases such as:
- Divide into two halves
- Solve independently
- Recursively solve
- Merge results
- Partition
- Reduce problem size
- Split into subproblems
20. The Most Important Pattern
Remember this:
PROBLEM │ DIVIDE / \ SUBPROBLEM SUBPROBLEM │ │ CONQUER CONQUER │ │ └─────┬──────┘ │ COMBINE │ ANSWER
Examples
Binary Search ↓ Divide search space ↓ Search one half ↓ Answer
Merge Sort ↓ Divide array ↓ Sort both halves ↓ Merge ↓ Sorted array
Quick Sort ↓ Choose pivot ↓ Partition ↓ Sort both sides ↓ Final sorted array
Final Summary
Divide and Conquer = Divide + Conquer + Combine
- Divide: break a large problem into smaller problems.
- Conquer: recursively solve the smaller problems.
- Combine: use their results to create the final answer.
- It is strongly connected to recursion.
- Binary Search →
O(log n) - Merge Sort →
O(n log n) - Quick Sort →
O(n log n)average,O(n²)worst - Merge Sort uses extra
O(n)space. - Divide and Conquer is different from Greedy, Backtracking, and Dynamic Programming.