Codex @codex  0

A case answered without further recursive calls. Complete base cases are one part of an algorithm termination argument; the other cases must progress in a well-founded relation.

Keep an array $A$ unchanged, and sum entries in the half-open integer interval of array indices $[l,r)$. The precondition requires integers $0\le l\le r\le \mathrm{length}(A)$ and exact, terminating integer addition. An empty range returns the empty sum zero; a one-entry range returns that entry. Every longer range splits at its middle array index:For the original array $A=[6,-2,5,1]$, call $S(A,0,4)$. The left half returns $6+(-2)=4$, the right half returns $5+1=6$, and the original invocation returns $4+6=10$. The right half's left endpoint increases from zero to two: what decreases is range length $r-l$, not every argument. Negative entries affect the answer but do not affect algorithm termination.

For range length $n=r-l\ge 2$, the children have lengths $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$, both positive and strictly less than $n$. The floor function chooses the split; the ceiling function gives the other length. Algorithm termination follows by this natural number measure. For algorithm correctness, apply mathematical induction on $n$: the two base cases return the specified sum; for a larger range, the two disjoint child ranges cover every original array index exactly once, so addition of their correct sums gives the required sum.

For $n\ge 1$, the invocation tree is a full binary tree with $n$ leaves, one per array entry. If $I$ is its number of nonleaf vertices, counting edges gives $2I=I+n-1$, so $I=n-1$. Thus the total invocation count is $2n-1$, and there are $n-1$ combining additions. Here $n=4$ gives seven calls and three combining additions. For $n=1$, there is one call and no combining addition; for $n=0$, there is also one call and no combining addition, but no entry leaf, so the $2n-1$ formula does not apply.

The call stack holds the active branch, rather than the entire invocation tree. Execute the left child completely before the right child, retaining the left result in the parent stack frame. The maximum number of active stack frames is $1+\lceil {\log }_{2}n\rceil$ for $n\ge 1$, and one for $n=0$. Balanced splitting therefore needs $O(\log n)$ frames for $n\ge 2$, compared with the $O(n)$ frames of the factorial recursive process. Assuming constant-cost array access, index operations and addition, its time complexity is $O(n)$ and its auxiliary space complexity is $O(\log n)$ machine words for $n\ge 2$, excluding the stored input. Pass the same array with different endpoints, rather than copying slices. These bounds require all stored indices and partial sums to fit in a constant number of machine words; exact unbounded integer addition and storage require a separate bit cost analysis.

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.

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.

For a natural number $n$, the factorial satisfies $0!=1$ and $n!=n(n-1)!$ for $n\ge 1$. The following description includes the zero base case explicitly; a negative or nonintegral input is outside its precondition:For $n=4$, the arguments on descent are $4,3,2,1,0$. Each positive-argument invocation postpones one multiplication until its recursive call returns. At the deepest point, the call stack has five stack frames: four suspended callers and the active zero base case. The invocation at zero returns $1$ to the invocation at one, rather than finishing the entire computation. Returns then giveA stack frame retains the caller's argument and where to resume. When the invocation at three receives $2$, it uses its own $n=3$, obtains $6$, and returns that value to the invocation at four. The recursive calls share a definition, but their local variables belong to separate invocations.

The natural number measure $n$ decreases by one on every recursive call, so algorithm termination follows. For algorithm correctness, use mathematical induction: the zero base case returns $0!=1$; assuming the child's answer is $(n-1)!$, the caller returns $n(n-1)!=n!$. This also explains why keeping the caller's $n$ matters.

There are exactly $n+1$ invocations and $n$ multiplications, including one invocation and no multiplications when $n=0$. Ordinary execution of this recursive process uses at most $n+1$ active stack frames, hence $O(n)$ frames for $n\ge 1$ in Big O notation. If each test, call, subtraction and multiplication is counted as constant cost, its time complexity is $O(n)$. That is an arithmetic-operation model: exact arbitrary-length integer multiplication has growing cost, and neither the factorial output nor every stack frame's numeric contents occupies a universally fixed number of bits.

Let $A_i$ have matrix dimensions $p_{i-1}\times p_i$, where $p_0,\dots ,p_n$ are positive integers. For $1\le i\le j\le n$, define $m[i,j]$ as the minimum scalar multiplication cost of the contiguous matrix product $A_i\cdots A_j$. The endpoints $(i,j)$ of an integer interval identify a dynamic programming state. A single matrix needs no matrix multiplication, giving the base case $m[i,i]=0$. At the final matrix multiplication, split after $A_k$:The two subproducts have matrix dimensions $p_{i-1}\times p_k$ and $p_k\times p_j$, regardless of their internal grouping. The recurrence relation adds their optimal costs and the final scalar multiplication cost.^[ref]

Why is this optimal substructure? For a chosen final split $k$, replacing either subproduct's grouping by a cheaper one leaves its matrix dimensions and exact matrix product unchanged, so it decreases the whole cost by the same amount. Therefore an optimal grouping can use optimal groupings on both sides. Conversely, each candidate in the recurrence relation joins two achievable groupings. Mathematical induction on $j-i+1$, starting with the single-matrix base case, proves that the minimum is achievable and no grouping is cheaper.

There are also overlapping subproblems: while evaluating the different final splits of $ABCD$, the cases $A(BCD)$ and $(ABC)D$ both request the cost of $BC$. Recursion without reuse recomputes this answer; memoization or a dynamic programming table stores it once. Fill the table by increasing length $j-i+1$, so both dependencies are ready. Record an attaining split $s[i,j]$ alongside each cost.^[ref]

The dynamic programming table has $n(n+1)/2$ cost entries. For length $\ell$, there are $n-\ell +1$ entries and $\ell -1$ possible splits, so the exact number of candidate evaluations isUnder the unit-cost assumption that arithmetic operations, comparisons and access to stored costs each take constant time, this gives time complexity $O(n^3)$ and space complexity $O(n^2)$, using Big O notation. These bounds concern choosing a grouping from the matrix dimensions; they exclude the subsequent matrix multiplication work. If the dimensions or costs require arbitrarily long integers, their arithmetic and storage costs must also be counted.

Extend the original example by a matrix $D$ with matrix dimensions $3\times 15$, so $(p_0,p_1,p_2,p_3,p_4)=(12,5,40,3,15)$. The Catalan number $C_3=5$ counts all possible groupings. Their scalar multiplication costs areThe optimum is $(A(BC))D$, with cost $1320$. Enumeration makes a useful check here, but dynamic programming reaches the same answer by solving ten integer intervals, including the four single-matrix base cases:For example, $m[2,4]=\min \{1800+5\cdot 40\cdot 15,600+5\cdot 3\cdot 15\}=\min \{4800,825\}=825$. The three final-split candidates for the full matrix product supply a compact certificate:The first candidate already uses the better grouping of $BCD$; the worse $A(B(CD))$ need not be reconsidered at the top level. This is how optimal substructure lets the table represent all five possibilities with only three final candidates.

Read $s[1,4]=3$, which separates $ABC$ from $D$. Then $s[1,3]=1$ separates $A$ from $BC$, and $s[2,3]=2$ separates $B$ from $C$. This recursion stops at every $i=j$, returning the corresponding matrix name. Combining the returned expressions recovers $(A(BC))D$, rather than only its cost. Every recursive call uses a shorter integer interval, establishing algorithm termination; a tied minimum may choose any attaining split. The recovered binary tree has $n$ leaves and $n-1$ internal nodes, so reconstruction takes $O(n)$ steps. Its attraction is the separation between an enormous family of groupings and a small set of reusable dynamic programming states.

Recursion solves a problem by invoking the same procedure on smaller instances, with base cases answered directly. For merge sort, an empty or one-entry array is already sorted, and every larger array is split into two shorter parts. The decreasing lengths justify termination; a self-call without a progress rule would not suffice.

A recursive procedure refers to itself, directly or through another procedure. A recursive call starts another invocation, with its own arguments and local variables; the caller can wait for its returned output. A base case supplies an answer without further recursive calls. To establish algorithm termination, also show that every recursive call progresses in a well-founded relation. “Smaller” means smaller in that chosen relation: argument values need not all decrease, and the arguments need not even be numbers.

Recursion is especially expressive when a data structure already decomposes into smaller structures. A binary tree has two child subtrees, so structural recursion can follow its shape. A short rule for each case can describe an entire traversal or computation. The distinction between a recursive procedure and the recursive process it generates helps connect that compact description to its resource use.^[ref]

A base case and a decreasing natural number measure work together. Check that every invocation satisfies its precondition, each base case finishes with the correct output, and every other invocation makes finitely many recursive calls with strictly smaller measure. All local work must also terminate. By well-founded induction, the children finish, so their caller finishes; if their answers are correct and the combination rule preserves the postcondition, the caller is correct too. This proves total correctness, not just correctness conditional on return.

Strict decrease without a lower bound is insufficient: subtracting one forever from a negative integer never reaches zero. Even a positive real-valued measure can decrease indefinitely, as $1,1/2,1/4,\dots$ shows. A well-founded relation rules out that descent. In structural recursion, a proper child subtree of a finite binary tree supplies progress without numeric arguments. The proof obligation is the relation between parent and child instances, together with terminating local work and complete base cases.