iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Divide & Conquer

By · Reviewed & last updated · Part of Data Structures & Algorithms

Divide-and-conquer splits a problem into smaller copies of itself, solves them recursively, and combines. It is the engine behind mergesort, quicksort, binary search, FFT, Karatsuba multiplication, and parallel reductions. The master theorem tells you the runtime: T(n) = a T(n/b) + f(n) -> O(?).

Three classic divide-and-conquer algorithms

EXAMPLE
# 1) Mergesort — O(n log n), stable
def mergesort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    left  = mergesort(a[:mid])
    right = mergesort(a[mid:])
    return merge(left, right)

def merge(a, b):
    out = []; i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:]); out.extend(b[j:])
    return out

print(mergesort([5, 2, 4, 6, 1, 3]))   # [1,2,3,4,5,6]

# 2) Quickselect — find the kth smallest in expected O(n)
import random
def quickselect(a, k):
    if len(a) == 1: return a[0]
    pivot = random.choice(a)
    lo = [x for x in a if x < pivot]
    hi = [x for x in a if x > pivot]
    eq = [x for x in a if x == pivot]
    if k < len(lo):                 return quickselect(lo, k)
    if k < len(lo) + len(eq):       return pivot
    return quickselect(hi, k - len(lo) - len(eq))

print(quickselect([7, 2, 9, 4, 1, 8, 3], 3))   # 4

# 3) Closest pair of points in 2D — O(n log n), divide on x
import math
def closest_pair(points):
    pts_sorted_x = sorted(points)
    pts_sorted_y = sorted(points, key=lambda p: p[1])
    return _closest(pts_sorted_x, pts_sorted_y)

def _closest(xs, ys):
    n = len(xs)
    if n <= 3:
        best = math.inf
        for i in range(n):
            for j in range(i+1, n):
                d = math.dist(xs[i], xs[j])
                if d < best: best = d
        return best
    mid = n // 2
    mid_x = xs[mid][0]
    left_xs  = xs[:mid]
    right_xs = xs[mid:]
    left_ys  = [p for p in ys if p[0] <  mid_x]
    right_ys = [p for p in ys if p[0] >= mid_x]
    dl = _closest(left_xs,  left_ys)
    dr = _closest(right_xs, right_ys)
    d  = min(dl, dr)
    strip = [p for p in ys if abs(p[0] - mid_x) < d]
    for i in range(len(strip)):
        # Only need to check the next 7 points by Shamos's bound
        for j in range(i+1, min(i+8, len(strip))):
            d = min(d, math.dist(strip[i], strip[j]))
    return d

print(closest_pair([(0,0),(3,4),(1,1),(7,7),(5,5)]))   # ~1.41

# 4) Master theorem applied
# Mergesort:     T(n) = 2 T(n/2) + O(n)            -> O(n log n)
# Binary search: T(n) = T(n/2) + O(1)              -> O(log n)
# Quickselect:   E[T(n)] = T(n/2) + O(n)           -> O(n) expected
# Karatsuba:     T(n) = 3 T(n/2) + O(n)            -> O(n^log2(3)) ~ O(n^1.585)
# Strassen:      T(n) = 7 T(n/2) + O(n^2)          -> O(n^log2(7)) ~ O(n^2.81)

Why it matters

When a divide-and-conquer problem hands you a recurrence, reach for the master theorem before guessing. T(n) = a T(n/b) + f(n) has three cases; matching f(n) to n^log_b(a) tells you the asymptotic without unrolling the recursion.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// Pattern: split → solve sub-problems → combine.
// Examples: merge sort, quick sort, FFT, Strassen matrix multiply.
Try it Yourself »

Discussion

Loading…