Divide-and-Conquer Algorithm: Concepts, Strategies, Steps, Complexity, and Classic Problems

Divide-and-conquer (D&C) is a fundamental algorithmic technique that solves a problem by recursively breaking it into smaller independent sub‑problems, solving each sub‑problem, and then merging the solutions.

The method works best when the problem size can be reduced to a threshold where a direct (ad‑hoc) solution is trivial, the sub‑problems exhibit optimal‑substructure, their solutions can be combined, and the sub‑problems are independent.

The generic D&C design pattern consists of three steps at each recursion level: step1: divide the original problem into k smaller independent sub‑problems , step2: solve each sub‑problem directly if small enough or recurse otherwise , and step3: merge the sub‑problem solutions into the final answer .

A typical recursive formulation is shown below:

Divide-and-Conquer(P)
if |P| ≤ n0 then return ADHOC(P)
divide P into P1, P2, …, Pk
for i ← 1 to k do yi ← Divide-and-Conquer(Pi)
T ← MERGE(y1, y2, …, yk)
return T

The time complexity of a D&C algorithm satisfies the recurrence T(n) = k·T(n/m) + f(n), where k is the number of sub‑problems, m is the factor by which the problem size shrinks, and f(n) is the cost of dividing and merging. Solving the recurrence (e.g., by the Master Theorem) yields the asymptotic growth of T(n).

Classic problems that can be solved efficiently with divide‑and‑conquer include binary search, large‑integer multiplication, Strassen’s matrix multiplication, the chessboard‑covering problem, merge sort, quicksort, linear‑time selection, the closest‑pair of points, round‑robin tournament scheduling, and the Tower of Hanoi.

When designing a D&C program, one typically follows a reasoning process analogous to mathematical induction: identify the base case solution, determine how the solution scales with larger inputs, formulate the recursive function, and then implement the recursive algorithm.