Divide and Conquer from Scratch (2026)
Divide and conquer is a powerful algorithmic paradigm that breaks a problem into smaller subproblems, solves them recursively, and combines the solutions. This approach is the foundation for many efficient algorithms including merge sort, quicksort, binary search, and Strassen's matrix multiplication. The key insight is that solving smaller subproblems can be more efficient than solving the original problem directly.
In this tutorial, we will implement the maximum subarray problem (Kadane's vs divide and conquer), closest pair of points, Strassen's matrix multiplication, and understand the Master Theorem for analyzing divide and conquer recurrences.
Maximum Subarray - Divide and Conquer
The maximum subarray problem finds the contiguous subarray with the largest sum. The divide and conquer approach splits the array into two halves. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. We find the maximum crossing subarray by expanding from the midpoint in both directions.
The recurrence is T(n) = 2T(n/2) + O(n), which solves to O(n log n) by the Master Theorem. Note that Kadane's algorithm solves this in O(n) time, making it more efficient. However, the divide and conquer approach demonstrates the paradigm well.
#include
#include
#include
using namespace std;
int maxCrossingSum(vector& arr, int low, int mid, int high) {
int leftSum = INT_MIN, sum = 0;
for (int i = mid; i >= low; i--) {
sum += arr[i];
leftSum = max(leftSum, sum);
}
int rightSum = INT_MIN; sum = 0;
for (int i = mid + 1; i <= high; i++) {
sum += arr[i];
rightSum = max(rightSum, sum);
}
return leftSum + rightSum;
}
int maxSubarray(vector& arr, int low, int high) {
if (low == high) return arr[low];
int mid = (low + high) / 2;
return max({maxSubarray(arr, low, mid),
maxSubarray(arr, mid+1, high),
maxCrossingSum(arr, low, mid, high)});
}
int kadane(vector& arr) {
int maxSoFar = arr[0], maxEnd = arr[0];
for (int i = 1; i < arr.size(); i++) {
maxEnd = max(arr[i], maxEnd + arr[i]);
maxSoFar = max(maxSoFar, maxEnd);
}
return maxSoFar;
} Closest Pair of Points
The closest pair of points problem finds the two points with the minimum distance in a 2D plane. A brute force approach takes O(n^2) time. The divide and conquer approach sorts points by x-coordinate, splits them into left and right halves, recursively finds the closest pair in each half, and then checks pairs that straddle the dividing line within a strip of width d.
The key insight is that points in the strip can be sorted by y-coordinate, and for each point, we only need to check a constant number of subsequent points (at most 7). This reduces the merging step to O(n), giving an overall complexity of O(n log n).
import math
def distance(p1, p2):
return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)
def brute_force(points):
min_dist = float('inf')
for i in range(len(points)):
for j in range(i+1, len(points)):
d = distance(points[i], points[j])
if d < min_dist: min_dist = d
return min_dist
def closest_pair_rec(px, py):
n = len(px)
if n <= 3: return brute_force(px)
mid = n // 2
mid_point = px[mid]
lx = px[:mid]; rx = px[mid:]
ly = [p for p in py if p[0] <= mid_point[0]]
ry = [p for p in py if p[0] > mid_point[0]]
dl = closest_pair_rec(lx, ly)
dr = closest_pair_rec(rx, ry)
d = min(dl, dr)
strip = [p for p in py if abs(p[0]-mid_point[0]) < d]
for i in range(len(strip)):
for j in range(i+1, min(i+7, len(strip))):
d = min(d, distance(strip[i], strip[j]))
return dStrassen's Matrix Multiplication
Strassen's algorithm multiplies two n x n matrices in O(n^2.807) time, faster than the naive O(n^3) approach. It divides each matrix into four n/2 x n/2 submatrices, performs 7 recursive multiplications (instead of 8), and combines the results cleverly. The key is reducing the number of multiplications at the cost of more additions.
Strassen's algorithm uses 7 multiplications and 18 additions for the submatrices, compared to 8 multiplications and 4 additions in the naive approach. The recurrence T(n) = 7T(n/2) + O(n^2) solves to O(n^log2(7)) which is approximately O(n^2.807).
public class Strassen {
static int[][] multiply(int[][] A, int[][] B) {
int n = A.length;
if (n == 1) return new int[][]{{A[0][0]*B[0][0]}};
int[][] A11=half(A,0,0), A12=half(A,0,n/2);
int[][] A21=half(A,n/2,0), A22=half(A,n/2,n/2);
int[][] B11=half(B,0,0), B12=half(B,0,n/2);
int[][] B21=half(B,n/2,0), B22=half(B,n/2,n/2);
int[][] M1=multiply(add(A11,A22),add(B11,B22));
int[][] M2=multiply(add(A21,A22),B11);
int[][] M3=multiply(A11,sub(B12,B22));
int[][] M4=multiply(A22,sub(B21,B11));
int[][] M5=multiply(add(A11,A12),B22);
int[][] M6=multiply(sub(A21,A11),add(B11,B12));
int[][] M7=multiply(sub(A12,A22),add(B21,B22));
return join(add(sub(add(M1,M4),M5),M7), add(M3,M5),
add(M2,M4), add(sub(add(M1,M3),M2),M6));
}
}Master Theorem
The Master Theorem provides a formula for solving divide and conquer recurrences of the form T(n) = aT(n/b) + O(n^d). If a < b^d, T(n) = O(n^d). If a = b^d, T(n) = O(n^d log n). If a > b^d, T(n) = O(n^log_b(a)). This theorem helps us quickly determine the time complexity of divide and conquer algorithms.
Examples: Binary search: T(n) = T(n/2) + O(1), a=1, b=2, d=0, so O(log n). Merge sort: T(n) = 2T(n/2) + O(n), a=2, b=2, d=1, so O(n log n). Strassen: T(n) = 7T(n/2) + O(n^2), a=7, b=2, d=2, so O(n^2.807).
import math
def master_theorem(a, b, d):
if a < b**d: return f"O(n^{d})"
elif a == b**d: return f"O(n^{d} log n)"
else: return f"O(n^{math.log(a)/math.log(b):.2f})"
print("Binary search:", master_theorem(1, 2, 0)) # O(log n)
print("Merge sort:", master_theorem(2, 2, 1)) # O(n log n)
print("Strassen:", master_theorem(7, 2, 2)) # O(n^2.81)
print("Karatsuba:", master_theorem(3, 2, 1)) # O(n^1.58)
def divide_and_conquer(problem):
if is_base_case(problem): return solve_directly(problem)
subproblems = divide(problem)
sub_results = [divide_and_conquer(sp) for sp in subproblems]
return combine(sub_results)Frequently Asked Questions
When to use divide and conquer?
Use when the problem can be broken into independent subproblems of similar type. Ideal for parallel processing. Examples: merge sort, quicksort, binary search, closest pair, Strassen multiplication.
What is the Master Theorem?
The Master Theorem solves recurrences T(n) = aT(n/b) + O(n^d). If a < b^d: O(n^d). If a = b^d: O(n^d log n). If a > b^d: O(n^log_b(a)). It provides quick complexity analysis.
Is divide and conquer always better?
Not always. For some problems, dynamic programming (O(n)) or greedy algorithms may be faster than divide and conquer (O(n log n)). Choose based on the problem's optimal substructure.
How is divide and conquer different from DP?
Divide and conquer breaks problems into independent subproblems and combines results. DP solves overlapping subproblems and stores results. D&C has no overlapping; DP has overlapping subproblems.
Originally published on Ayodhyyya. Last updated June 1, 2026.