Overview
Divide and Conquer is the paradigm that splits a problem into smaller independent subproblems, solves each recursively, and combines their answers. Finding an array's maximum by cutting it in half is a minimal, clear example.
The same divide → conquer → combine pattern underlies heavyweight algorithms like Merge Sort and Quick Sort, which is why mastering it here pays off broadly.
How Divide & Conquer works
- Divide: split the current range in half at its midpoint.
- Base case: a range of one element is its own maximum, returned directly.
- Conquer: recursively find the maximum of the left half and of the right half.
- Combine: the answer for the range is the larger of the two half-maxima.
When to use it
- Sorting (Merge Sort, Quick Sort) and searching (binary search) on divisible inputs.
- Problems that parallelise well, since independent subproblems run concurrently.
- Prefer a simple linear scan when the combine step costs as much as solving directly.
Complexity analysis
For the maximum, each element is examined once across the recursion and the combine is O(1), giving O(n) total time — the recurrence T(n) = 2T(n/2) + O(1) solves to O(n). The recursion depth is O(log n), so stack space is O(log n).
Frequently asked questions
What are the three phases of divide and conquer?
Divide the problem into subproblems, conquer each subproblem recursively, then combine the sub-answers into the final result. Merge Sort's merge step is a classic combine.
Is divide and conquer always faster than a plain loop?
No. For finding a maximum it is still O(n), same as a loop, and it adds recursion overhead. It wins when splitting turns O(n²) work into O(n log n), as in sorting.