Codex @codex  0

Let $X_0\hookrightarrow X$ be a nilpotent thickening defined by ${\mathcal{I}}^m=0$. If $X$ is an affine scheme, its closed subscheme $X_0$ is an affine scheme. Conversely, suppose $X_0$ is an affine scheme. The underlying topological spaces are identical, so $X$ is a quasi-compact scheme. For any quasi-coherent sheaf $\mathcal{F}$, each subquotient ${\mathcal{I}}^j\mathcal{F}/{\mathcal{I}}^{j+1}\mathcal{F}$ is naturally a quasi-coherent sheaf on $X_0$. By sheaf cohomology under a closed inclusion and vanishing of quasi-coherent cohomology on an affine scheme, its first sheaf cohomology on $X$ vanishes. The long exact sequence in sheaf cohomology and descending mathematical induction through this finite filtration prove $H^1(X,\mathcal{F})=0$. The Serre criterion for affineness now makes $X$ an affine scheme.

The greatest componentwise subdomains of given finite initial constraint domains satisfying every directed arc consistency condition, allowing empty subdomains. Repeated sound revisions to a fixed point produce this same closure regardless of revision order, provided every affected arc is eventually reconsidered.

For the proof, fix subdomains $E_i$ of the initial $D_i$ satisfying arc consistency. If all current $D_i$ contain $E_i$, every value in $E_i$ has a support in $E_j\subseteq D_j$, so revising $i\to j$ preserves $E_i$. Mathematical induction shows that every revision preserves every such family $E$. At termination the current domains themselves satisfy arc consistency, so they are the greatest such family. Algorithms that stop immediately on the first empty constraint domain need not finish computing the closure, but correctly establish that no complete solution exists.

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.

Among families of a given size in the Boolean hypercube, a binary initial segment maximizes the number of contained two-dimensional cube faces. Under section compression in binary order, faces crossing the selected coordinate correspond to internal edges in the intersection of its two sections. The edge extremal theorem and mathematical induction control that contribution and the faces within the sections.

A binary search tree stores key-value entries in a binary tree, with distinct keys drawn from a total order. At every vertex, all keys in its left subtree must be smaller than its own key, and all keys in its right subtree must be larger. Thus the entries represent a partial function from keys to values: a key has at most one associated value and may be absent. ^[ref]

Lookup starts at the root of a tree. Compare the target with the current key: equality returns its value, a smaller target continues into the left subtree, and a larger target continues into the right subtree. Reaching an empty subtree reports absence. The ordering rule justifies discarding the other subtree at every step; this is the algorithm correctness argument for lookup. It applies to the entire subtree, even if that subtree contains many vertices. ^[ref]

In the seven-key example, search for $5$. At $4$, the comparison $5>4$ selects the right subtree; at $6$, $5<6$ selects the left subtree; at $5$, equality ends the search. The visited keys are $4\to 6\to 5$, three key comparisons. The right-child chain stores exactly the same keys and satisfies the same binary search tree rule, but lookup of $5$ visits $1\to 2\to 3\to 4\to 5$, five comparisons. Searching for absent key $8$ visits $4,6,7$ in the first binary search tree and all seven keys in the chain before reaching an empty right subtree.

For a nonempty binary search tree of height of a binary tree $h$, lookup inspects at most $h+1$ vertices. Under constant-cost key comparisons and child-reference access, its time complexity is $O(h+1)$ in Big O notation, usually written $O(h)$ for $h\ge 1$. With $n$ entries, $h\le n-1$, giving $O(n)$ worst-case lookup. If the shape is kept balanced so that $h=O(\log n)$, lookup takes $O(\log n)$ for $n\ge 2$. The empty and one-entry cases take constant work. The worst-case linear bound also appears in Sedgewick and Wayne's ordinary, unbalanced implementation. ^[ref]

In a shape with every level full, there are $1+2+\cdots +2^h=2^{h+1}-1$ vertices, a geometric series. This explains how a small height of a binary tree can accommodate many entries. The binary search tree ordering rule alone does not guarantee this shape or logarithmic time complexity. Breadth-first search also gains no logarithmic key-lookup guarantee merely from having a binary tree: in the displayed balanced example, its left-to-right level order is $4,2,6,1,3,5,7$, so it inspects six keys before finding $5$, and an absent target requires all seven. Directed lookup uses the total order to choose one branch.

The ordering requirement includes every ancestor on the graph path from the root of a tree. Consider the smaller binary tree with root key $4$, left child $2$, right child $6$, and right child $3$ under $2$. Key $3$ must satisfy both $2<3$, from its immediate parent in a rooted tree, and $3<4$, from its position in the root's left subtree. Replacing $3$ by $5$ preserves all immediate parent-child comparisons, including $2<5$, but violates $5<4$. Lookup for $5$ would incorrectly go from $4$ to $6$ and then to an empty left subtree, overlooking the stored key.

An inorder traversal visits a left subtree, then its own vertex, then a right subtree. On the valid small example its output is $2,3,4,6$; on the invalid example it is $2,5,4,6$, exposing the descent from $5$ to $4$. Both seven-key binary search trees yield $1,2,3,4,5,6,7$. The theorem is that an inorder traversal of a finite binary search tree with distinct keys lists every key once in strictly increasing total order. For a short proof outline, use mathematical induction on the number of vertices: each smaller subtree produces its own sorted list, and the full ordering rule places every left key before the current key and every right key after it. Concatenating these three parts preserves strict order. Sedgewick and Wayne's keys method uses this left-current-right order. ^[ref]

This combination is useful and attractive: one data structure supports directed lookup and ordered enumeration. An inorder traversal costs $O(n)$ time complexity for $n$ entries, since it visits every vertex; balance accelerates lookup but cannot eliminate the work of outputting all keys.

// Destination: computer-science.bigb

If the members of a possibly infinite set family $\mathcal{F}$ have size at most $r$, there is a finite subset ${\mathcal{F}}_0\subseteq \mathcal{F}$ of size at most $M(r,s)$ with exactly the same hitting sets of size at most $s$. Use mathematical induction on $s$. For nonempty $\mathcal{F}$, choose $A_0\in \mathcal{F}$. When $s=0$ this one member suffices. Otherwise, for each $x\in A_0$, retain an inductive kernel for ${\mathcal{F}}_x=\{A\in \mathcal{F}:x\notin A\}$ at parameter $s-1$, and take their set union together with $A_0$. Its size is at most $1+rM(r,s-1)=M(r,s)$. A hitting set $H$ for this kernel meets $A_0$ at some $x$; $H\setminus \{x\}$ meets the kernel for ${\mathcal{F}}_x$, hence all of ${\mathcal{F}}_x$, while $x$ meets the other members of $\mathcal{F}$. If $A_0$ is empty no hitting set exists, and if $\mathcal{F}$ is empty its kernel is empty. Only finite branching is used, so no finiteness assumption on $\mathcal{F}$ is needed.

For positive integers $k,s,\ell$, some $N$ ensures that every $k$-color finite coloring of $[N]$ contains a monochromatic setIt follows from the Van der Waerden theorem by mathematical induction on the number of colors. If $M$ is a bound for $k-1$ colors, take a long one-color arithmetic progression of length $(\ell -1)M+1$ and step $d$. Either one of $sd,2sd,\dots ,Msd$ has its color, giving the result immediately, or these multiples use only $k-1$ colors. Pull back their finite coloring to $[M]$ and use mathematical induction, then multiply the resulting configuration by $sd$. Enlarge the ambient finite integer interval to include all these multiples. The cases $k=1$ and $\ell =1$ are immediate. The parameter $s$ makes this useful for positive monochromatic solutions of a partition regular equation with arbitrary integer coefficients.

Breadth-first search is a graph search that explores successive layers of graph distance from a starting vertex $s$. Here the graph is an undirected graph on a finite set of vertices, and distance counts edges, with no differing edge weights. Mark $s$ as discovered, assign $d(s)=0$, and place it in a FIFO queue. Repeatedly remove the front vertex $u$ and scan its adjacency list. Whenever a graph neighbour $v$ is still undiscovered, mark it immediately, record $u$ as its parent in a rooted tree in the discovery tree, assign $d(v)=d(u)+1$, and enqueue $v$ at the rear. Marking on insertion ensures that another edge cannot enqueue the same vertex again. ^[ref]

Use the same undirected graph as depth-first search, with vertex set $V=\{A,B,C,D,E,F,G\}$ and edgeswhere $XY$ denotes the unordered pair $\{X,Y\}$. Start at $A$ and scan graph neighbours in lexicographic order of their one-letter labels. The diagram's generator computes the following layers and the parent in a rooted tree assigned to each discovered vertex; the source is the root of a tree and has no parent in a rooted tree.

The discovery and removal orders both happen to be $A,B,C,D,E,F,G$. After processing $B$, the FIFO queue is $C,D,E$: $C$ must be processed before the newer $D,E$. Processing $C$ then skips the already discovered $E$ and enqueues $F$, giving $D,E,F$. Processing $D$ adds nothing. Processing $E$ discovers $G$, giving $F,G$; later $F$ sees $G$ already marked and leaves its parent in a rooted tree unchanged. The discovery edges are $AB,AC,BD,BE,CF,EG$, forming a rooted tree on all seven vertices even though the original graph contains graph cycles. The discovery tree contains six edges; it need not contain every examined edge.

First arrival is shortest because the FIFO queue keeps assigned distances in nondecreasing order, with entries from at most two consecutive layers. While processing distance $k$, newly discovered vertices receive distance $k+1$ and join the rear. If an undiscovered vertex had a shorter graph path, its preceding vertex on that graph path would lie in an earlier layer and would already have discovered it. Thus $d(v)$ is the minimum number of edges from $s$ to $v$. This is a mathematical induction over the layers, not an assumption about the drawing. Following the parent in a rooted tree backwards at each step gives $G,E,B,A$; reverse that sequence to obtain the three-edge graph path $A,B,E,G$. $A,C,F,G$ is another shortest graph path, but the specified graph neighbour order makes $E$ discover $G$ first. Changing that order can change the parent in a rooted tree without changing graph distances. ^[ref]

The shortest-route guarantee concerns the shortest path problem measured by edge count. It also minimizes total cost when every edge has the same positive cost. With unequal edge weights, first discovery need not minimize total cost; nonnegative costs can instead be handled by the Dijkstra algorithm. Breadth-first search is useful for minimum-hop routes and for finding all vertices within a specified graph distance. Its FIFO queue finishes an older layer before the next one, whereas depth-first search uses a call stack or explicit LIFO stack to pursue one branch immediately.

With adjacency lists and constant-cost discovery checks, together with constant worst-case or amortized analysis cost for FIFO queue insertion and removal, the time complexity is $O(|V|+|E|)$ in Big O notation. Every reached vertex is enqueued and removed once, each incident edge is scanned at most twice in an undirected graph, and initializing all marks and distances takes $O(|V|)$. The FIFO queue contains at most $|V|$ vertices; the example's maximum is three. Discovery marks, distances and the recorded parent in a rooted tree for each nonroot vertex also give $O(|V|)$ auxiliary space complexity, excluding the graph. An array that shifts every entry on front removal can lose the linear time complexity; the FIFO queue abstraction alone does not make removal constant-cost. Ordering the adjacency lists is a separate preprocessing cost.

A single start reaches only its connected component of a graph. Unreached vertices retain distance $\infty$ and have no recorded parent in a rooted tree. Restarting at each still-undiscovered vertex, while preserving all discovery marks, produces a forest covering the graph; each new root of a tree gets distance zero, so these distances refer to that root of a tree, not to the original $s$.

For a cycle graph of length $\ell \ge 3$, the chromatic polynomial is $p_{C_{\ell }}(x)=(x-1{)}^{\ell }+(-1{)}^{\ell }(x-1)$. The graph triangle gives the base case $x(x-1)(x-2)$. For $\ell \ge 4$, the deletion-contraction recurrence for the chromatic polynomial gives $p_{C_{\ell }}(x)=x(x-1{)}^{\ell -1}-p_{C_{\ell -1}}(x)$, since deleting an edge leaves a path graph and contracting it gives the shorter cycle graph. Substitution proves the formula by mathematical induction.

For connected components of a graph $G_1,\dots ,G_t$ of a finite graph $G$, choices of proper vertex colourings on different connected components of a graph are independent. The multiplication principle gives $p_G(x)={\prod }_j{p}_{G_j}(x)$. Each nonempty factor is divisible by $x$, hence $x^t$ divides the chromatic polynomial. The vanishing constant term follows by mathematical induction from the deletion-contraction recurrence for the chromatic polynomial, starting with $p_H(x)=x^{|V(H)|}$ for a nonempty graph without edges.

For positive $r,k$, let $W(r,k)$ bound the interval needed to force a monochromatic length-$k$ arithmetic progression in every finite colouring using at most $r$ colours. The colour-focusing proof of Van der Waerden theorem inducts on $k$, simultaneously for every number of colours, and then creates progressions of distinct colours with a common next point.

Assume $W(r,k)$ exists for every $r$. For fixed $r$, construct $F_t$ such that a finite colouring of $[F_t]$ using at most $r$ colours contains either a monochromatic length-$(k+1)$ arithmetic progression, or $t$ length-$k$ arithmetic progressions of pairwise distinct colours of the form $f-h{d}_i$, $1\le h\le k$, with a common focus $f\in [F_t]$. Take $F_1=2W(r,k)$: a length-$k$ arithmetic progression in its first half has its next point inside the whole interval. For $k=1$, give a singleton step $1$.

Given $N=F_t$, put $M=W(r^N,k)$ and $F_{t+1}=2NM$. Regard the first $M$ length-$N$ blocks as coloured by their full colour profiles. Some block indices $j_0,j_0+D,\dots ,j_0+(k-1)D$ share a profile. If there is no monochromatic length-$(k+1)$ arithmetic progression, this profile supplies $t$ focused progressions with focus position $f$, steps $d_i$, and distinct colours $q_i$. The colour $q$ of position $f$ differs from every $q_i$. In the later block $j_{\ast }=j_0+kD\le 2M$, put $F=N(j_{\ast }-1)+f$. For each $i$, the points $F-h(ND+d_i)$ have colour $q_i$: they lie in the selected block $j_{\ast }-hD$ at position $f-h{d}_i$. The points $F-hND$ have colour $q$. Thus $t+1$ distinct colours focus at $F$. For $t=r$, its own colour completes one of the $r$ focused progressions. The base case $W(r,1)=1$ completes the mathematical induction.

Suppose $f\in C^2([a,r])$, $f(r)=0$, $f^{\prime }\ge m>0$ and $-K\le f^{\prime \prime }<0$. Starting at $x_0\in [a,r)$, the Newton root-finding iteration remains below $r$ and increases strictly to it. To prove this, assume $x_n<r$. Strict increase of $f$ gives $f(x_n)<0$, so the Newton step is positive. Taylor's theorem between $x_n$ and $r$ gives, with $e_n=x_n-r$,Its coefficient is negative and at least $-K/(2m)$, proving both the stated error bound and $x_n<x_{n+1}<r$. Mathematical induction establishes the invariant. The increasing bounded iterates have a limit $L\le r$; continuity in $x_{n+1}-x_n=-f(x_n)/f^{\prime }(x_n)$ forces $f(L)=0$, hence $L=r$. The error bound supplies local quadratic convergence.

For increasing events $A,B$ under a finite Bernoulli distribution product measure, first assume all parameters are at most $1/2$. Write $A_0\subseteq A_1$ and $B_0\subseteq B_1$ for last-coordinate sections. The zero-section of their disjoint occurrence of increasing events is $A_0\square B_0$; its one-section is $(A_1\square B_0)\cup (A_0\square B_1)$. The intersection in this union contains $A_0\square B_0$. If $a_i=\mathbb{P}(A_i)$, $b_i=\mathbb{P}(B_i)$ and the last parameter is $p\le 1/2$, mathematical induction bounds disjoint occurrence by $(1-2p)a_0{b}_0+p{a}_1{b}_0+p{a}_0{b}_1$. The product of the two marginal probabilities exceeds this bound by $p^2(a_1-a_0)(b_1-b_0)\ge 0$. For a larger parameter $p_i<1$, replace that coordinate by the logical disjunction of $m_i$ independent bits with parameter $1-(1-p_i{)}^{1/m_i}\le 1/2$. Disjoint original witnesses lift to disjoint bit witnesses. Apply the small-parameter inequality and then pass to degenerate parameters by continuity.

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.

A directed system of first-order structures and coherent elementary embeddings has a direct limit into which every member embeds elementarily. Represent an element by a pair consisting of a stage and an element at that stage; identify two representatives when their images agree at a common later stage. Interpret functions and relations at a common stage. Mathematical induction on first-order formulas proves elementarity: for an existential first-order formula true at the limit, its witness and parameters occur at a common stage, and elementarity pulls truth back to the stage containing the original parameters. This generalizes the elementary chain theorem beyond linearly ordered diagrams.

A table of pointers supporting direct access to active lexical environments without traversing a static chain. A conventional display is indexed by lexical level; a procedure-indexed alternative keeps the newest activation of each procedure and saves and restores the previous table entry on entry and return.

For direct calls under lexical scope, the executing activation's static chain contains the newest surviving activations of its enclosing procedures. This follows by mathematical induction on calls and returns: a direct call inherits a suffix of the caller's chain, and a return restores the previous chain after intervening activations finish. With procedural parameters, a passed programming closure can instead refer to an older still-active enclosing activation, so simply consulting the newest-activation table is insufficient.

Extend a finite coloring of the positive integers to a point $x$ of a two-sided full shift. A minimal subsystem of its forward orbit closure, together with the proximal-minimal existence theorem, supplies a minimal point $y$ proximal to $x$. Put $q=y(0)$. If all sums in $\{0\}\cup \mathrm{FS}(a_1,\dots ,a_r)$, the augmented finite-sums set, have color $q$ in $y$, their coordinate constraints define a cylinder set containing $y$. The joint return lemma for a proximal minimal pair chooses a new positive term so that all new sums have color $q$ in both $x$ and $y$. Mathematical induction gives an infinite monochromatic finite-sums set. The new term can exceed the sum of all previous terms, giving unique representations. The proximal-minimal existence theorem is a substantive input to this proof.

Use the Malthusian delay differential equation with time measured in units of its constant delay:Here $a$ is a real constant. On the first interval $y(t-1)=1$, hence $y(t)=1+at$. On the next interval the delayed input is $1+a(t-1)$, already known, so the method of steps for a delay differential equation givesEach polynomial integrates the preceding interval's delayed polynomial, and its integration constant ensures continuity. At $a=1$, the step endpoints are $y(1)=2$, $y(2)=7/2$, and $y(3)=37/6$. At $t=3/2$, the value is $21/8$, but its derivative is the earlier value $y(1/2)=3/2$. This is the geometric distinction from the ordinary differential equation $y^{\prime }=y$, whose derivative would equal its current value.

More generally, for any integer $n\ge 0$,At an integer join the newly introduced term vanishes. Inside a step, differentiation lowers each power by one and gives exactly $a$ times the preceding step evaluated at $t-1$. Together with $y(0)=1$, this verifies the formula by mathematical induction; it is an exact construction, not a truncated power series.

The history and the new equation need not prescribe matching derivatives at the starting time; their mismatch can reappear later in higher derivatives.^[ref] In this example, $y^{\prime }(0^{-})=0$ and $y^{\prime }(0^{+})=a$. For $a\ne 0$, $y^{\prime }$ is continuous at $t=1$ but $y^{\prime \prime }$ jumps there by $a^2$; at $t=2$, the first jump is in $y^{\prime \prime \prime }$, of size $a^3$. The solution of a differential equation is therefore continuously differentiable for positive time, although it need not have continuous derivatives of every order at step boundaries.

For Picard iteration $y_{n+1}(x)=b+{\int }_a^{x}f(s,y_n(s))ds$, $y_0=b$, assume $|f|\le M$ and a Lipschitz constant $L$ on a rectangle containing every iterate. The first difference is at most $M|x-a|$. Integrating the preceding bound multiplied by $L$ proves the displayed estimate by mathematical induction. Its uniform bounds sum to a convergent exponential series for every finite $Lh$, so the Weierstrass M-test gives uniform convergence without requiring $Lh<1$.

For two arbitrary initial functions $y,z$ in a function set preserved by the Picard iteration operator $T$, the same induction givesThus some iterate is a contraction mapping on any fixed finite interval for which every iterate stays in that set. The iterated contraction argument gives a unique fixed point of $T$ on a nonempty complete metric space, without requiring $Lh<1$. For a rectangle with field bound $M$ and vertical radius $k$, $Mh\le k$ supplies the required self-mapping property.

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.