Section Overview

Divide and Conquer: break a problem into similar subproblems, solve each subproblem recursively, then combine the results.

Every algorithm in this section produces a recurrence of the form $T (n) = a T (n / b) + O (n^{d})$ , which the Master Theorem below solves in closed form — it’s the one tool that ties this whole section together.

Divide and Conquer (The Paradigm)

Break a problem into similar subproblems.
Solve each subproblem recursively.
Combine the subproblem results into a solution for the original problem.
Key detail: subproblems must be smaller instances of the same problem — that’s what makes the recursion terminate and what makes Master Theorem-style analysis applicable in the first place.

Multiplying n-bit Numbers (Classic Recursive Approach)

Suppose we want to multiply two $n$ -bit numbers, $n$ a power of 2. Split each into left/right halves of $n /2$ bits each:

x y x y = 2^{n /2} x_{L} + x_{R} = 2^{n /2} y_{L} + y_{R} = 2^{n} x_{L} y_{L} + 2^{n /2} (x_{L} y_{R} + x_{R} y_{L}) + x_{R} y_{R}

The boxed terms are recursive calls at half the size.

Algorithm 14 Algorithm Multiply

Input: $n$ -bit intergers $x$ and $y$

Output: the product $xy$

procedure multiply( $x,y$ )

if $n=1$ then

return $xy$

$x_L, x_R$ and $y_L, y_R$ are the left-most and right-most $n/2$ bits of $x$ and $y$ respectively

$P_1$ = multiply( $x_L, y_L$ )

$P_2$ = multiply( $x_L, y_R$ )

$P_3$ = multiply( $x_R, y_L$ )

$P_4$ = multiply( $x_R, y_R$ )

return $P_1 \times 2^n + (P_2 + P_3) \times 2^{n/2} + P_4$

Time Complexity: $T (n) = 4 T (n /2) + O (n)$ (3 additions + 2 bit shifts of $O (n)$ -bit integers, plus 4 recursive calls) → Master Theorem with $a = 4, b = 2, d = 1$ : since $a > b^{d}$ ( $4 > 2$ ), $T (n) = O (n^{l o g_{2} 4}) = O (n^{2})$ .
Key detail: this is asymptotically no better than grade-school multiplication — the 4-way recursive split doesn’t actually help until you reduce the number of subproblems (see Karatsuba below).

Karatsuba’s Algorithm (Multiply KS)

Algorithm 15 Multiply KS

Input: $n$ -bit integers $x$ and $y$

Output: the product $xy$

procedure multiplyKS( $x,y$ )

if $n=1$ then

return $xy$

$x_L, x_R$ and $y_L, y_R$ are the left-most and right-most $n/2$ bits of $x$ and $y$ respectively

$R_1$ = multiplyKS( $x_L, y_L$ )

$R_2$ = multiplyKS( $x_R, y_R$ )

$R_3$ = multiplyKS( $(x_L + x_R)(y_L + y_R)$ )// $(x_L + x_R)(y_L + y_R) = x_Ly_L + x_Ly_R + x_Ry_L + x_Ry_R$

return $R_1 \times 2^n + (R_3 - R_1 - R_2) \times 2^{n/2} + R_2$

Time Complexity: $T_{K S} (n) = 3 T_{K S} (n /2) + O (n)$ → Master Theorem with $a = 3, b = 2, d = 1$ : since $a > b^{d}$ ( $3 > 2$ ), $T_{K S} (n) = O (n^{l o g_{2} 3}) \approx O (n^{1.585})$ .
Key detail: the trick is computing $(x_{L} + x_{R}) (y_{L} + y_{R})$ once and subtracting off $R_{1}, R_{2}$ to recover the two cross terms $x_{L} y_{R} + x_{R} y_{L}$ — turning 4 recursive multiplications into 3, which is what drops the exponent below 2.

Master Theorem

If $T (n) = a T (\frac{n}{b}) + O (n^{d})$ for constants $a > 0, b > 1, d \geq 0$ , then

$T (n) \in {O (n^{d}) if a < b^{d} O (n^{d} lo g n) if a = b^{d} O (n^{l o g_{b} a}) if a > b^{d}$

Solving the Recurrence

After $k$ levels of recursion, there are $a^{k}$ subproblems, each of size $n / b^{k}$ . Work at level $k$ :

$O ((\frac{n}{b ^{k}})^{d}) a^{k} = O (n^{d} (\frac{a}{b ^{d}})^{k})$

After $lo g_{b} n$ levels, subproblem size shrinks to 1 (the base case), so the total is the sum over all levels:

$T (n) = O (n^{d} \sum_{k = 0}^{l o g_{b} n} (\frac{a}{b ^{d}})^{k})$

This is a geometric series with ratio $r = \frac{a}{b ^{d}}$ .

Proof (Three Cases)

Case 1 — $a < b^{d}$ ( $r < 1$ ): the series converges to a constant, so $T (n) = O (n^{d})$ .

Case 2 — $a = b^{d}$ ( $r = 1$ ): every term equals 1, so the sum is just the number of terms:

$T (n) = O (n^{d} \sum_{k = 0}^{l o g_{b} n} 1^{k}) = O (n^{d} lo g_{b} n)$

Case 3 — $a > b^{d}$ ( $r > 1$ ): the sum is exponential and grows proportional to its last term:

$T (n) = O (n^{d} (\frac{a}{b ^{d}})^{l o g_{b} n}) = O (n^{l o g_{b} a})$

Recall $\sum_{k = 0}^{n} r^{k} = \frac{r ^{n + 1} - 1}{r - 1} = O (r^{n})$

Deterministic vs. Randomized Approaches

Sorting and Selection each have a deterministic and a randomized solution, trading a worse worst-case bound for a simpler algorithm and better typical-case performance:

	Deterministic	Randomized
Sorting	Computer Science Introduction/Algorithms/Divide and Conquer/Merge Sort — $O (n lo g n)$	Quick Sort — Best: $O (n lo g n)$ , Worst: $O (n^{2})$ , Average: $O (n lo g n)$
Selection	Deterministic Selection (Median of Medians) — $O (n)$	QuickSelect — Best: $O (n)$ , Worst: $O (n^{2})$ , Average: $O (n)$

Quick Reference Table

Algorithm	Recurrence	Master Theorem Case	Closed-Form Runtime
Classic Multiply	$T (n) = 4 T (n /2) + O (n)$	$a > b^{d}$ ( $4 > 2$ )	$O (n^{2})$
Karatsuba (Multiply KS)	$T (n) = 3 T (n /2) + O (n)$	$a > b^{d}$ ( $3 > 2$ )	$O (n^{l o g_{2} 3}) \approx O (n^{1.585})$

Notes in This Section

Note	One-line description
Computer Science Introduction/Algorithms/Divide and Conquer/Binary Search	Halves the search space each comparison on a sorted array; $O (lo g n)$
Cook-Toom-k Algorithm	Generalizes Karatsuba’s trick to split into $k$ parts instead of 2, trading extra combine-step overhead for fewer recursive multiplications
Deterministic Selection	Median-of-medians (BFPRT) — splits into groups of 5 to construct a provably-good pivot, guaranteeing $O (n)$ worst case without randomization
Sorting	Foundational note for this family ― the decision tree argument for the $Ω (n lo g n)$ comparison-sort lower bound
Computer Science Introduction/Algorithms/Divide and Conquer/Merge Sort	Splits the array in half, recursively sorts each half, merges the two sorted halves; $O (n lo g n)$
Quick Sort	Partitions around a pivot, recursively sorts each side; $O (n lo g n)$ expected, $O (n^{2})$ worst case
QuickSelect	Quick Sort-style partitioning used to find the $k^{t h}$ smallest element directly, via a random pivot; $O (n)$ expected, $O (n^{2})$ worst case
Selection	The general “find the $k^{t h}$ smallest element” problem, plus the shared in-place `Partition with Pivot` subroutine; QuickSelect and Deterministic Selection are the two algorithms solving it
Two Runners	Binary search for the “turning point” where a slower-starting runner overtakes a faster one — a discrete analogue of the Intermediate Value Theorem; $O (lo g n)$

Jason's Notebook

Explorer

Divide and Conquer

Divide and Conquer (The Paradigm)

Multiplying n-bit Numbers (Classic Recursive Approach)

Karatsuba’s Algorithm (Multiply KS)

Master Theorem

Solving the Recurrence

Proof (Three Cases)

Deterministic vs. Randomized Approaches

Quick Reference Table

Notes in This Section

References / Links

Binary Search

Cook-Toom-k Algorithm

Deterministic Selection

Merge Sort

Quick Sort

QuickSelect

Selection

Sorting

Two Runners

Recent Notes

Robotics

Knowledge Vault

Backlinks

Graph View

Table of Contents