Divide and Conquer

Divide and conquer is an algorithm-design paradigm in computer science that solves a problem by breaking it into smaller instances, solving those instances, and assembling their results into a solution to the original problem. The decomposition is usually repeated through recursion until the remaining instances are small enough to solve directly. Its effectiveness depends on how the subproblems are constructed and how much work is required to divide and combine them. Classic applications include sorting, searching, and matrix multiplication. (introcs.cs.princeton.edu)

Structure and correctness

A divide-and-conquer algorithm normally has three stages:

1. Divide: construct smaller subproblems from the current instance.
2. Conquer: solve these subproblems recursively, or directly when a base case is reached.
3. Combine: use their solutions to obtain the answer for the current instance.

The stages need not contribute equal amounts of work. Some algorithms perform most of their work during division; others require an substantial combination step. Subproblems must become smaller under a suitable measure so that recursive calls eventually reach a base case. (ocw.mit.edu)

For example, merge sort divides an array into two halves, sorts each half, and merges the sorted results. Arrays containing zero or one element are already sorted. Its correctness can be expressed using mathematical induction: the base cases are correct, and merging correctly sorted smaller arrays produces a correctly sorted larger array. This illustrates the connection between recursive structure and mathematical proof. (introcs.cs.princeton.edu)

Running-time analysis

The time complexity of a divide-and-conquer algorithm is commonly described by a recurrence relation. When each instance produces $a$ subproblems of size approximately $n/b$, a standard model is

where $f(n)$ represents the nonrecursive work of division and combination, and constant-size instances take constant time. Here $n$ must denote the relevant size measure: for square-matrix multiplication, for example, it is often the matrix dimension. (ocw.mit.edu)

A recursion tree represents recursive calls as nodes and distributes their costs across levels. For merge sort, two half-size calls and a linear-time merge give

Each level contributes linear total work, and there are logarithmically many levels. This is an example of computational complexity analysis using asymptotic notation, including big-O notation and the tight-bound notation $\Theta$. (ocw.mit.edu)

The master theorem provides bounds for important classes of such recurrences. In the common special case $f(n)=\Theta(n^d)$, comparing $d$ with $\log_b a$ identifies whether the leaves, all levels equally, or the upper levels dominate the total cost. Recurrences with input-dependent splits, such as those arising in quicksort, require additional analysis rather than direct substitution into this equal-size model. (ocw.mit.edu)

Representative algorithms

Sorting. Quicksort partitions an array around a pivot and recursively sorts the resulting regions. Unlike merge sort, its main work occurs before the recursive calls; little subsequent combination is necessary. Balanced partitions yield efficient recursion, whereas repeatedly extreme partitions can produce quadratic running time. Random pivot selection or initial random shuffling gives a randomized algorithm with expected $O(n\log n)$ running time. (algs4.cs.princeton.edu)

Searching. Binary search compares a target with the middle element of a sorted array and continues in only the relevant half. Its recurrence is $T(n)=T(n/2)+\Theta(1)$, giving logarithmic running time. It is often presented as a one-subproblem version of divide and conquer: unlike merge sort, it does not solve both halves. (ocw.mit.edu)

Matrix multiplication. Strassen’s algorithm divides each matrix into four blocks and computes seven recursive block products instead of the eight used by straightforward block multiplication. Additional block additions and subtractions yield

and therefore $\Theta(n^{\log_2 7})$, approximately $\Theta(n^{2.807})$, arithmetic operations. The improvement comes from reducing the number of recursive multiplications, not merely from partitioning the matrices. (ocw.mit.edu)

Fourier computation. The radix-2 fast Fourier transform separates even-indexed and odd-indexed inputs into two half-size transforms, then combines them using symmetry properties of the discrete Fourier transform. For power-of-two lengths, this gives $\Theta(n\log n)$ operations instead of the quadratic cost of direct evaluation. The same decomposition can be described through the even- and odd-degree coefficients of a polynomial. (introcs.cs.princeton.edu)

Relationship to dynamic programming

Divide and conquer and dynamic programming both construct solutions from smaller subproblems. Their usual distinction concerns repeated work. Classical divide-and-conquer decompositions produce separate subproblem instances; dynamic programming handles overlapping subproblems by storing and reusing their solutions. Memoization implements this reuse within a recursive formulation. Independence here concerns computational dependencies, not probabilistic independence. (ocw.mit.edu)

Parallel execution and implementation

Independent recursive calls can run concurrently, making divide and conquer a useful structure for parallel computing. Parallel performance depends on both total work and span, the longest chain of dependent operations. A computation can have many recursive tasks yet offer limited speedup if its division or combination stages remain sequential. (cs.cmu.edu)

Practical implementations often stop recursion above the smallest possible base case and switch to a simpler sequential method. This reduces function-call or task-scheduling overhead; sorting implementations may use insertion sort for small subarrays. Partition balance also matters, because poor splits can increase running time and recursion depth. Memory use depends on the implementation: array merge sort commonly uses auxiliary storage, whereas in-place quicksort avoids a separate partition array but still requires storage for pending recursive calls. (cs.cmu.edu)