Divide and Conquer: Recursive Decomposition, Recurrences, and Optimization

Divide and Conquer (D&C) is an algorithmic paradigm that breaks a complex problem into smaller, independent subproblems of the same type, solves them recursively, and combines their solutions to form the global result.

⚡ Quick Dive

The Three-Step Lifecycle

          [ Original Problem of Size n ]
                       │
         ┌─────────────┴─────────────┐
      (Divide)                    (Divide)
         ▼                           ▼
[ Subproblem (n/2) ]        [ Subproblem (n/2) ]
         │ (Conquer)                 │ (Conquer)
         ▼                           ▼
[ Solution A ]              [ Solution B ]
         └─────────────┬─────────────┘
                   (Combine)
                       ▼
          [ Final Combined Solution ]

Classic Divide & Conquer Algorithms

Algorithm Problem Recurrence Time Complexity Combine Cost
Binary Search Search in sorted array $T(n) = T(n/2) + O(1)$ $O(\log n)$ $O(1)$
Merge Sort Stable sorting $T(n) = 2T(n/2) + O(n)$ $O(n \log n)$ $O(n)$
QuickSort In-place sorting $T(n) = 2T(n/2) + O(n)$ (Avg) $O(n \log n)$ $O(1)$ (Work in Divide)
Karatsuba Multiplication Large integer multiplication $T(n) = 3T(n/2) + O(n)$ $O(n^{\log_2 3}) \approx O(n^{1.585})$ $O(n)$
Strassen's Algorithm Matrix multiplication $T(n) = 7T(n/2) + O(n^2)$ $O(n^{\log_2 7}) \approx O(n^{2.807})$ $O(n^2)$
Closest Pair of Points Computational geometry $T(n) = 2T(n/2) + O(n)$ $O(n \log n)$ $O(n)$

📖 Extended Guide

1. Karatsuba Fast Integer Multiplication

Multiplying two $n$-digit numbers naively takes $O(n^2)$ elementary multiplications.

Let $X = X_1 \cdot 10^{n/2} + X_0$ and $Y = Y_1 \cdot 10^{n/2} + Y_0$. $$X \cdot Y = X_1 Y_1 \cdot 10^n + (X_1 Y_0 + X_0 Y_1) \cdot 10^{n/2} + X_0 Y_0$$

Karatsuba reduces the 4 recursive multiplications to 3 multiplications:

  1. $z_2 = X_1 \cdot Y_1$
  2. $z_0 = X_0 \cdot Y_0$
  3. $z_1 = (X_1 + X_0)(Y_1 + Y_0) - z_2 - z_0 = X_1 Y_0 + X_0 Y_1$

$$X \cdot Y = z_2 \cdot 10^n + z_1 \cdot 10^{n/2} + z_0$$

  • Recurrence: $T(n) = 3T(n/2) + O(n) \implies O(n^{\log_2 3}) \approx O(n^{1.585})$.

2. Strassen's Matrix Multiplication

Standard matrix multiplication of two $n \times n$ matrices requires $n^3$ multiplications.

Strassen partitioned matrices $A$ and $B$ into four $n/2 \times n/2$ submatrices and calculated 7 matrix products ($M_1$ through $M_7$):

  • Recurrence: $T(n) = 7T(n/2) + O(n^2) \implies O(n^{\log_2 7}) \approx O(n^{2.807})$.

This forms the theoretical basis for modern high-performance linear algebra kernels (BLAS / LAPACK).

3. Closest Pair of Points in 2D Plane ($O(n \log n)$)

Problem: Given $n$ points in a 2D plane, find the two points with minimum Euclidean distance. Naive comparison takes $O(n^2)$.

Divide & Conquer Approach:

  1. Sort points by X-coordinate once ($O(n \log n)$).
  2. Divide point set by vertical midpoint line $L$ into Left and Right halves.
  3. Recursively find minimum distance $\delta_L$ in Left and $\delta_R$ in Right: $\delta = \min(\delta_L, \delta_R)$.
  4. Combine Step: Check points within strip $[L - \delta, L + \delta]$. Sort strip by Y-coordinate; for each point, we only need to inspect at most the next 7 points!
  5. Total Time: $T(n) = 2T(n/2) + O(n) = O(n \log n)$.

4. Divide & Conquer vs. Dynamic Programming

Characteristic Divide & Conquer Dynamic Programming
Subproblem Independence Disjoint & Independent (e.g., left/right array halves) Overlapping Subproblems (subproblems share identical sub-subproblems)
Computation Reuse Subproblems solved once without memoization Subproblem solutions stored in memo table/tabulation array
Call Stack Natural recursive tree structure Top-Down recursion + cache OR Bottom-Up iterative table
⌂ All Guides