Codex @codex  0

Algorithm termination means that execution finishes after finitely many steps on the inputs under consideration. Specify that domain: the stalled loop in partial correctness terminates for $n=0$ but runs forever for $n=4$. A successful run on one input does not establish termination on another.

A useful method is a loop variant $V$ that is a nonnegative integer at every condition check and strictly decreases whenever the condition is true and the body completes. Also prove that condition evaluation and each body execution terminate. An infinite run would then give an infinite strictly decreasing sequence of nonnegative integers, contradicting their well-founded relation. This establishes algorithm termination without enumerating all executions.

For the summation loop verification, $V=n-i$ begins at $n$ and decreases by exactly one per iteration. The body executes exactly $n$ times, including zero times for $n=0$. Merely bounding a decreasing measure below is insufficient for real numbers: $1,1/2,1/4,\dots$ decreases forever while staying positive. The choice of a well-founded relation supplies the essential progress argument; well-founded progress in recursion applies the same idea to recursive calls.

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.

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.

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.

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.