Divide-and-conquer algorithm

A divide-and-conquer algorithm divides a problem into smaller instances, solves them using recursion, and combines their answers. In merge sort, the division makes two contiguous halves, and the merge algorithm combines the resulting sorted arrays. The important design step is finding a combination rule cheaper than solving the whole problem afresh.

Halving the input is only one part of the design. The number of recursive calls and the work outside those calls determine whether the smaller instances actually save time. Divide-and-conquer combination cost keeps these quantities separate; the divide-and-conquer product ledger shows how an algebraic identity changes the number of required calls in Karatsuba multiplication.

For algorithm correctness, specify the meaning of each returned answer, prove the base cases, and show that combining correct smaller answers gives the required output. Induction then proves correctness, provided every recursive call progresses towards a base case. The combination rule must reconstruct everything the caller needs: two sorted halves alone are not a sorted array, and four digit blocks alone are not their integer product.

An integer-valued problem size requires integer subproblem sizes and a base case. For the displayed unequal split with $n\ge 2$, both children have positive size less than $n$, and $1/4\le m/n\le 1/2$. The entropy potential for a divide-and-conquer recurrence therefore supplies a uniform positive potential decrease. The squared sizes satisfy $m^2+(n-m{)}^2\le 5n^2/8$, which similarly closes a quadratic inductive hypothesis when the work at the root is $n^2$.

The minimum and maximum of a nonempty array can be found with at most $\lceil 3n/2\rceil -2$ pairwise comparisons. Compare consecutive pairs once, retaining smaller entries as minimum candidates and larger entries as maximum candidates. If an entry is unpaired, put it into both candidate sets. Each candidate set has $\lceil n/2\rceil$ entries, and finding one extremum on $r$ entries uses $r-1$ comparisons. Thus the total is $\lfloor n/2\rfloor +2(\lceil n/2\rceil -1)$, equal to the stated bound; the singleton case uses zero. Balanced divide-and-conquer algorithms can perform both candidate reductions. Pairing is important: arbitrary equal splitting with only a two-element base case does not attain this comparison count at every size.

An entry of a finite array which strictly exceeds each existing immediate neighbour. At either endpoint only one neighbour is tested, and the unique entry of a singleton qualifies vacuously. For distinct entries, a divide-and-conquer algorithm finds such an entry in $O(\log n)$ time. Maintain an index interval whose left endpoint exceeds the excluded entry immediately to its left, if any, and whose right endpoint exceeds the excluded entry immediately to its right, if any. If a midpoint has a larger internal neighbour, recurse towards it; the comparison supplies the new boundary inequality. Otherwise the midpoint exceeds its internal neighbours and the boundary inequalities cover any external neighbour. Halving the interval and preserving this recursion invariant proves correctness and the bound.

An entry occurring strictly more than half the time in an array must occur strictly more than half the time in at least one half: otherwise the two frequency bounds sum to at most half the whole length. Recursively find each half's possible majority element, then verify at most two candidates over the whole subarray using only equality tests. Induction proves correctness, and linear combination work over a balanced recursion tree gives worst-case $\Theta (n\log n)$ time. A tagged absent result avoids confusing failure with a valid element.

The combination cost is the work needed to reconstruct an answer from the returned smaller answers. In a time complexity calculation, also count partitioning the input, preparing arguments, and other work outside recursive calls. Write their total as $g(n)$ for a size-$n$ call. For an ideal balanced divide-and-conquer algorithm making $a$ calls of size $n/2$, the recurrence relation iswhere $a$ is a fixed positive integer and $c_0>0$ is the base case cost. Take $n=2^k$, a power of two, so the size becomes one after exactly $k$ divisions. This is a model of total sequential work: all $a$ smaller calls contribute, even if a machine could run some simultaneously.

At level $j$, there are $a^j$ calls, each of size $n/2^j$. Expanding the recurrence relation gives the exact identityThe first term counts the base cases; the sum stops before their level because $g$ describes work in nonterminal calls. This separates depth, number of calls, and local work. Merge sort has two smaller calls and a linear merge algorithm, giving $T(n)=2T(n/2)+O(n)=O(n\log n)$ in Big O notation. The MIT notes derive this by summing equal work across levels, and contrast it with the same two-way split followed by quadratic local work.^[ref]

For the first constructed model, set $a=2$, $c_0=1$ and $g(s)=s$. Every internal level costs $2^j(n/2^j)=n$, while the leaves cost $n$. Thus $T(n)=n{\log }_{2}n+n$, giving $T(16)=80$. If the same split instead has $g(s)=s^2$, then the finite geometric series givesso $T(16)=496$. The root alone already costs $n^2$ in this second model. Smaller arguments do not eliminate expensive reconstruction. These are stipulated operation counts, rather than measured running times or exact merge sort instruction counts.

Binary search has a different saving: after its comparison, only one half remains a candidate. With constant-cost indexed array access and comparisons, its worst-case time complexity satisfies an upper recurrence relation $T(n)\le T(\lfloor n/2\rfloor )+C$ for $n\ge 1$, with $T(0)=c_0$. There is one continuing branch, rather than two. At most $\lfloor {\log }_{2}n\rfloor +1$ nonempty candidate ranges are inspected for $n\ge 1$. Copying the retained half into a fresh array on every step would add linear work at that step and lose this logarithmic bound. The shrinking range and its representation both matter.

Splitting two integers in positional notation gives $x=aq+b$ and $y=cq+d$, where $q=B^m$ shifts a block by $m$ numeral digits in fixed radix $B\ge 2$. The distributive property givesComputing $ac,ad,bc,bd$ separately needs four block multiplications. Merely halving the operands therefore gives an ideal recurrence relation $F(n)=4F(n/2)+O(n)$, still with quadratic time complexity. The Karatsuba three-product identity instead computes $ac$, $bd$ and $(a+b)(c+d)$, recovering the middle coefficient by two subtractions. The MIT notes present precisely this four-product versus three-product distinction.^[ref]

For an original small example, multiply $47$ by $63$. Set $B=q=10$, $a=4$, $b=7$, $c=6$, $d=3$. Four separate block products would give $ac=24$, $ad=12$, $bc=42$, $bd=21$. The three-product calculation isThe crucial reuse is that $u$ and $v$ supply the outer coefficients and also remove the unwanted terms from $w$. There is no need to compute $ad$ and $bc$ separately. Expanding $w=ac+ad+bc+bd$ proves the identity. Induction extends it to Karatsuba multiplication once each smaller block product is correct and Karatsuba recursion termination supplies decreasing sizes and complete base cases.

The operation model matters. Let $n$ count numeral digits in fixed radix $B$, and count single-digit multiplication, addition, subtraction and copying as constant-cost operations. The nonrecursive work on size-$n$ operands is $O(n)$: it includes forming sums, positional shifts and Karatsuba carry handling. Treating an arbitrarily large integer multiplication as one operation would hide the very saving being studied. The coefficients $24,54,21$ above must be shifted and added; concatenating them does not give $2961$.

In the ideal equal-half model, Karatsuba multiplication has $K(n)=3K(n/2)+O(n)$. At depth $j$ its additional work is at most a constant times $n(3/2{)}^j$, and its leaf count is $3^k=n^{{\log }_{2}3}$ for $n=2^k$. A geometric series gives $K(n)=O(n^{{\log }_{2}3})$, where ${\log }_{2}3\approx 1.585$. Four recursive products would instead give $4^k=n^2$ leaves. Saving one block product repeatedly changes the exponent, even though the combination requires extra addition and subtraction.

For the literal sum-based version, each operand sum can occupy one extra numeral digit. Its worst-case upper recurrence relation is $K(n)\le 3K(\lceil n/2\rceil +1)+Cn$ for a nondecreasing cost envelope, above a fixed base case threshold of at least three digits. Karatsuba digit-operation cost proves that this extra digit preserves the exponent; Karatsuba operand splitting handles odd lengths and leading zero padding. For signed integers, apply the nonnegative procedure to their absolute values and restore the sign. The small ledger establishes an exact identity, while Karatsuba practical crossover explains why it alone cannot predict a speedup for two-digit operands.