Divide-and-conquer algorithm

Definition

Let $I$ be a set of problem instances with a size function $\abs{\cdot} \colon I \to \N$ . A divide-and-conquer algorithm on $I$ is a recursive algorithm given by:

a direct method that solves every instance of size at most a constant $n_0$ ;
a divide step that maps each instance $x$ with $\abs{x} > n_0$ to finitely many instances $x_1, \dots, x_a$ of $I$ with $\abs{x_i} < \abs{x}$ ;
a combine step that computes the solution of $x$ from the solutions of $x_1, \dots, x_a$ .

On an instance of size greater than $n_0$ , the algorithm divides, solves each $x_i$ recursively, and combines.

Remarks

Clause 2 makes the recursion terminate, since the sizes strictly decrease in $\N$ . If dividing and combining cost $f(n)$ and each subproblem has size about $n/b$ , the running time satisfies the recurrence $T(n) = a\,T(n/b) + f(n)$ .

Example: Karatsuba multiplication of two $n$ -digit numbers writes $x = x_1 B + x_0$ and $y = y_1 B + y_0$ with $B$ a power of the base of about half the length, and uses $x y = x_1 y_1 B^2 + \big((x_1 + x_0)(y_1 + y_0) - x_1 y_1 - x_0 y_0\big) B + x_0 y_0$ . This needs three recursive products of about half size instead of four, so $T(n) = 3T(n/2) + O(n)$ and $T(n) = O(n^{\log_2 3})$ .

Non-example: a recursion that reduces an instance of size $n$ to an instance of the same size $n$ fails clause 2, and it need not terminate.

Reading path

To understand this page from the ground up, read these 3 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`ZYDZME1BH3`
URI	`m2://ZYDZME1BH3`
Kind	definition
Writing	W0 stub
MSC	68W40, 68W01
Defines	Divide-and-conquer algorithm
Uses	Algorithm, Recurrence relation
Changed	3 November 2026

Divide-and-conquer algorithm

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here