Divide and Conquer
DSA · Algorithm Techniques
Theory
Divide and conquer splits a problem into smaller independent sub-problems of the same type, solves them recursively, and combines their answers. Merge sort, quick sort, binary search and fast exponentiation all follow this pattern. The running time is often described by recurrences such as T(n) = 2T(n/2) + O(n), which solves to O(n log n).
Why we use it
Splitting the work reduces complexity dramatically and allows parallel processing of independent parts.
When to use it
Use it for sorting, searching, fast power, counting inversions, closest pair of points and large-scale parallel computations (MapReduce follows the same idea).
How it works
- solve(problem)
- Small enough? Yes: Solve directly. No: Divide into subproblems.
- Solve each subproblem recursively
- Combine the results
- Return
Syntax
solve(problem):
if small: return direct answer
parts = split(problem)
results = [solve(p) for p in parts]
return combine(results)
T(n) = 2T(n/2) + O(n) -> O(n log n)Example
def power(base, exp):
if exp == 0:
return 1
half = power(base, exp // 2)
if exp % 2 == 0:
return half * half
return half * half * base
def max_subarray(nums, lo, hi):
if lo == hi:
return nums[lo]
mid = (lo + hi) // 2
best_left = total = float("-inf")
s = 0
for i in range(mid, lo - 1, -1):
s += nums[i]; best_left = max(best_left, s)
best_right, s = float("-inf"), 0
for i in range(mid + 1, hi + 1):
s += nums[i]; best_right = max(best_right, s)
return max(max_subarray(nums, lo, mid), max_subarray(nums, mid + 1, hi), best_left + best_right)
print("2^30 =", power(2, 30))
data = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Max subarray sum:", max_subarray(data, 0, len(data) - 1))Key points
- Divide, conquer, combine
- Sub-problems are independent
- Recurrences give the complexity
- Basis of merge sort and quick sort