Codex @codex  0

An algorithm is a finite, precise procedure for transforming an input into an output.

Here "finite" refers to the description: a short algorithm can perform arbitrarily many steps on increasingly large inputs. Solving a computational problem additionally requires termination and the specified output on every permitted input. State assumptions explicitly: binary search requires a sorted array.

An algorithm is an idea that can have implementations in different programming languages. Its explanation should make three things visible: the permitted inputs, the rule for each step, and the meaning of the returned output. Algorithm correctness then separates finding the right answer from eventually finishing; time complexity asks how much work finishing requires.

A particularly useful design question is: what knowledge survives each step? In binary search, it is the location of every possible match inside the remaining candidate range. Writing that fact as a loop invariant turns an intuitive shortcut into a procedure whose discarded candidates can be justified. This often helps discover the algorithm, rather than merely check it afterward.

Partial correctness means that, if the algorithm terminates on a permitted input, its output meets the formal specification. Total correctness additionally requires algorithm termination on every permitted input.

A precondition $P$ describes permitted starting circumstances; a postcondition $Q$ describes the required result. Partial correctness says that starting with $P$ and finishing implies $Q$. Total correctness also guarantees finishing. A loop invariant supplies the connection between these conditions during repeated steps.^[ref]

Correctness is relative to a formal specification. Returning the first entry of an array correctly implements "return the first entry", but fails "return the maximum" on $[3,1,4,4,2]$. A fast wrong answer does not acquire algorithm correctness from its time complexity. Numerical closeness matters only when the formal specification allows an approximation. Software testing and test coverage provide evidence about selected executions; they do not by themselves establish algorithm correctness for every permitted input.

Constructing an algorithm that meets a stated specification. Choices such as divide-and-conquer algorithms, dynamic programming and greedy algorithms organize the construction; an algorithm correctness argument establishes that the result meets the specification.

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 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

Computer science studies how information can be represented and transformed by algorithms, and what those transformations can achieve. Its central questions connect mathematics to practical design: what answer should a procedure produce, why is it correct, and how much work does it require as its input grows? Computability theory asks which tasks can be solved at all; computational complexity theory asks what resources a solution needs.

The beauty is that choosing a representation can change what is feasible. Finding a name among a million entries sounds like a million checks. Store the entries in a sorted array, and binary search needs at most twenty middle-entry comparisons. The order makes each unsuccessful comparison eliminate a whole region of possibilities. A data structure supplies useful organization; an algorithm exploits it; time complexity explains the resulting savings.

Algorithm correctness covers every permitted input, including absent names and empty collections. Time complexity predicts scaling; statistical program profiling investigates a particular implementation.

For a deterministic binary operation on an abstract data type, let $f$ be its specified operation on abstract values and $F$ the implementation on concrete states. For every permitted valid input pair $(r,s)$, require bothThe first condition preserves the representation invariant. The second makes a commutative diagram: either execute $F$ and then apply the abstraction function, or apply the abstraction function to both inputs and then execute the abstract operation $f$; both paths reach the same value. These conditions state functional correctness of a completed operation; termination is an additional obligation for algorithm correctness.^[ref]

For addition in the unreduced rational representation, chooseFor example, $F((1,2),(1,3))=(5,6)$ represents $5/6$, precisely the sum of $1/2$ and $1/3$. The short correctness argument uses nonzero denominators: $b\ne 0$ and $d\ne 0$ imply $bd\ne 0$, preserving the representation invariant, and

Now consider an incorrect implementation that uses addition on the numerators and multiplication on the denominators:It preserves the representation invariant for every valid input pair because its denominator is still $bd\ne 0$. Yet $B((1,2),(1,3))=(2,6)$ represents $1/3$, not the specified sum $5/6$. Even perfect checks of the representation invariant before and after this call would miss the error: the result is a legal representation of the wrong rational number.

The incorrect operation also exposes an accidental dependence on representation. Replace $(1,2)$ by the equivalent state $(2,4)$ while keeping $(1,3)$. The correct operation gives $(10,12)$, still representing $5/6$; the incorrect operation gives $(3,12)$, representing $1/4$ instead of its previous $1/3$. A correct addition must yield the same abstract result for equivalent inputs, although its concrete outputs may differ. This is why checks against the formal specification should compare abstract values, including unreduced representations and representations with a negative denominator, rather than demand identical stored pairs.

The calculation assumes exact integers. An implementation with bounded storage must additionally specify how it handles products and sums outside its supported range; the mathematical argument alone does not establish its functional correctness. The bounded queue with encapsulation illustrates the corresponding need to account for returned status values and failed operations, alongside the abstract state transition.

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.

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.

Changing the number of hash buckets and reassigning stored records using the new bucket-index hash function. Amortized analysis of rebuilding and expected value bounds for subsequent lookup address different costs.

Rebuild the balanced example from load factor of a hash table with $m^{\prime }=16$ while keeping exactly the same twelve records. Under $h_m(k)=k\mathrm{mod}m$, keys $0,\dots ,7$ retain their indices, whereas keys $8,9,10,11$ move from hash buckets $0,1,2,3$ to hash buckets $8,9,10,11$. The new chain lengths are twelve ones followed by four zeros; ${\alpha }^{\prime }=12/16=3/4$. Copying the old eight chain heads and adding eight empty heads would leave those four moved keys unreachable by the new lookup rule.

For a short algorithm correctness outline, allocate the new array, visit every old record once, compute its new bucket index, and link it into that hash bucket. At every step, each transferred record is stored exactly once at the index prescribed by the new hash function. Finishing the visit therefore preserves every key-value association and makes the new lookup rule valid. Direct transfer can skip duplicate searches because the old one-value-per-key map already established distinct equivalence classes; rebuilding is not twelve new user insertions.

Under constant-cost hashing, linking and slot initialization, separate chaining rebuilding takes $O(n+m+m^{\prime })$ time complexity: initialize $m^{\prime }$ new heads, examine $m$ old heads, and transfer $n$ records. For doubling, $m^{\prime }=2m$, this is $O(n+m)$ in Big O notation. It is $O(n)$ when the resize policy makes $m$ proportional to $n$, but an enormous mostly empty old array can make scanning its heads dominate. Growing capacity can lower $\alpha$ without shortening a particular chain: the concentrated keys $0,16,\dots ,176$ all remain in hash bucket $0$ after growth from eight to sixteen.

For an insertion-only sequence starting empty, choose initial capacity $m_0=8$ and double before a genuinely new key would make $n>m$. The first three growths occur before inserting records $9,17,33$ and transfer $8,16,32$ existing records. If $N=33$ distinct records are inserted, the transfer count is $8+16+32=56$. More generally, the transferred old capacities form a geometric series; if the last is $M<N$, their sum is $2M-m_0<2N$. Initializing and scanning these geometrically growing arrays also costs $O(N)$ in total, giving $O(1)$ amortized rebuilding overhead per insertion. A triggering insertion still pays for its whole rebuild.^[ref]

The illustrative twelve-record resize above is an explicitly requested rebuild, not a growth triggered by this threshold policy. Checking for an equal key before growing also prevents a value replacement from triggering unnecessary growth. To combine resizing overhead with expected constant insertion time complexity, separately impose the collision and constant-cost assumptions in load factor of a hash table. Amortized analysis distributes rebuilding costs over operations; it does not randomize a poor hash function or bound a single operation's latency. With deletions, separate the grow and shrink thresholds; for example, growing when full and halving at one-quarter live occupancy leaves room for many operations between opposite rebuilds.^[ref]

// Target: computer-science.bigb

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

The loop invariant just before inspecting index $i$ is: $0\le i\le n$, and no entry at an index $k<i$ matches $x$. Initially $i=0$, so there are no earlier entries. A failed equality test extends the excluded region by one position and preserves the loop invariant. A successful equality test at index $i$ establishes a match; the loop invariant establishes that it is the first one. At exhaustion, $i=n$ and every entry has failed, so the absent result is correct. The number $n-i$ of remaining entries decreases after each failed equality test, proving termination for a finite sequence. Together these establish algorithm correctness under the assumptions that the input is stable and each equality test terminates. No step of the argument compares the relative order of values.

A data structure representing a sequence through linked list nodes and links between them. In the singly linked representation used here, each linked list node holds an item and a next reference to its successor. head identifies the first linked list node; the final next is null, meaning no successor. An empty linked list has head = null. Sedgewick and Wayne use this representation to implement both a stack and a FIFO queue. ^[ref]

For $A\to B\to C$, place the linked list nodes at conceptual computer memory positions $40,12,76$, respectively. These deliberately separated labels describe a toy layout, not actual pointer values. The sequence order comes from the links, not increasing positions. To read index $2$, begin at head and follow two next references. For index $i$, this takes $i$ link-following steps and $O(1+i)$ time complexity, hence $O(n)$ in the worst case for $n$ linked list nodes, under the constant-cost operations assumed for the array example. ^[ref]

Suppose a reference to the existing linked list node $B$ is already known. To insert a fresh linked list node $X$ after it, first set X.next = B.next, preserving the old successor $C$, and then set B.next = X. The result is $A\to B\to X\to C$; none of the old items moves. Reversing these assignments would read the newly changed B.next and set X.next = X, losing the route to $C$ from head. This is a two-update algorithm correctness argument, rather than a claim that finding the insertion location is free.

The two pointer updates take $O(1)$ time in Big O notation. The complete insertion has $O(1)$ time complexity if the predecessor is already known, allocating and initializing the fixed-size linked list node costs $O(1)$, and copying its item has constant cost. Finding $B$ from head can instead cost $O(n)$; a position described only by an index does not confer the constant-cost advantage. This makes a linked list useful when an algorithm already holds the needed linked list node, or repeatedly works at the front as a stack does.

Deletion similarly needs the incoming link: to remove $X$ after known $B$, set B.next = X.next. A reference to $X$ alone does not identify its predecessor in this singly linked representation. The head is a special case: after checking for a nonempty linked list, remove it with head = head.next. If a tail reference is also maintained, deleting the only linked list node must clear that reference too; a stored length must also be updated. Removing a linked list node from the sequence and reclaiming its storage are separate responsibilities. ^[ref]

There are practical costs beyond Big O notation. Each singly linked linked list node needs a successor reference in addition to its item; separate allocation may add further overhead, while an array can reserve unused capacity. Consecutive array slots can make a scan reuse nearby contents already brought into a memory cache; separated linked list nodes can make link following wait for successive computer memory fetches. These are layout-dependent effects, not a guarantee that every array operation beats every linked list operation on every machine. An array of references can still lead to scattered objects, and linked list nodes can be allocated close together. ^[ref]

A statement true whenever execution reaches a chosen point in a loop, usually immediately before its condition is tested. Establish it initially, preserve it through each iteration, and combine it with the exit condition to establish algorithm correctness. Termination needs a separate argument.^[ref]

Write $I$ for the loop invariant, $B$ for the condition, $P$ for the precondition, and $Q$ for the postcondition. Prove that initialization under $P$ establishes $I$, that a completed body starting with $I$ and $B$ restores $I$, and that $I$ with false $B$ implies $Q$.^[ref]

In the prefix maximum correctness example, the loop invariant remembers exactly the maximum of the processed prefix and the valid index bounds. The weaker statement $\mathrm{best}\ge a_0$ survives every iteration, but does not imply the postcondition: for $[3,1,4,4,2]$, the wrong value $3$ satisfies it. A useful loop invariant retains enough information to recover the answer when the condition becomes false.

The merge algorithm combines two finite sorted sequences under the same total order, retaining every entry exactly once. Keep a position at the first unconsumed entry, or "head", of each input. While both heads exist, compare their keys, append the smaller head to the output, and advance only that head's position. On equality take the left head. Once either sequence is exhausted, append the other remainder without further key comparisons. Empty inputs therefore require no head comparisons. The MIT notes illustrate this two-head combination step.^[ref]

For example, the merge algorithm applied to $(1,4,7)$ and $(2,3,8,9)$ returns $(1,2,3,4,7,8,9)$:

The head pairs $(1,2)$, $(4,2)$, $(4,3)$, $(4,8)$ and $(7,8)$ select $1,2,3,4,7$ respectively. After the fifth comparison the left sequence is empty, so $(8,9)$ is appended. Seven entries are written, but only five head comparisons occur: tests for exhaustion and appending the remainder are separate operations. This distinction makes the example's count smaller than the bound $3+4-1=6$.

For nonempty inputs of lengths $m,n$, each head comparison consumes exactly one entry. After $m+n-1$ such removals at most one entry remains, so both heads cannot still exist. Hence the merge algorithm uses at most $m+n-1$ head comparisons. The bound can be attained: $(1,3,5)$ and $(2,4,6,7)$ require six head comparisons before the left sequence is exhausted. With constant-cost comparisons, access and copying, writing all $m+n$ entries gives time complexity $O(m+n)$ in Big O notation. Writing a separate output array needs $m+n$ entry slots; the two positions require only constant additional storage.

The merge algorithm is useful whenever two already ordered collections must become one: it reads each input only forwards. This works with arrays and linked lists, without needing access to arbitrary middle positions. Choosing left on ties preserves each input's internal order and places equal left entries before equal right entries, which is the combination rule needed for stable sorting in merge sort.

The loop invariant behind algorithm correctness is that the emitted prefix is sorted, contains exactly the consumed entries, and every emitted key is at most every unconsumed key. Each sorted sequence has its smallest remaining key at its head, so the smaller of the two heads is safe to append. The invariant survives each removal; when one sequence ends, the other sorted remainder is safe to append in full. Each comparison removes an entry, so termination follows from the finite input lengths.

// Target: computer-science.bigb

Merge sort is a divide-and-conquer algorithm that sorts a finite array by splitting it into contiguous halves, sorting each half using recursion, and combining the two sorted arrays with the merge algorithm. An empty or one-entry array is returned immediately. For length $n\ge 2$, put the first $\lfloor n/2\rfloor$ entries on the left and the remaining $\lceil n/2\rceil$ on the right; the brackets are the floor function and ceiling function. Always choose the left head on equal keys to obtain stable sorting. This is the split, sort, combine structure taught in the MIT lecture notes.^[ref]

Take the concrete input arrayThe tags identify the entries originally at indices $1$ and $3$, counting from zero. Both keys are $2$; the tags are never compared. Reading downward in the figure follows the splits, then the returned sorted arrays. Arrows show dependencies; the level layout groups independent calls rather than giving their chronological execution order.

The first two halves are $(7,2_a,5,2_b)$ and $(9,1,4,3)$. Their pairs split into one-entry base cases. Applying the merge algorithm gives the following fully worked return levels; each number in the last column counts only comparisons between two available heads.

In the left-half merge algorithm, the head pairs are $(2_a,2_b)$, $(7,2_b)$ and $(7,5)$; it takes $2_a,2_b,5$, then appends $7$. In the final merge algorithm, the head pairs are $(2_a,1)$, $(2_a,3)$, $(2_b,3)$, $(5,3)$, $(5,4)$, $(5,9)$ and $(7,9)$. It takes $1,2_a,2_b,3,4,5,7$, then appends $9$. Thus this precise version makes $4+6+7=17$ head comparisons and, ignoring identity tags, returns $(1,2,2,3,4,5,7,9)$.

The elegance of merge sort is that it creates exactly the structure its next step needs: two smaller sorted arrays make the larger ordering inexpensive. Once the whole array is sorted, equal keys are adjacent and binary search can serve repeated queries. Stable sorting also retains information that the keys alone do not express. If the left-half merge algorithm instead takes the right head on the $2_a=2_b$ tie, it returns $(2_b,2_a,5,7)$; the keys are sorted but stable sorting has failed.

For time complexity, assume each key comparison, entry access and entry copy has constant cost. The merge algorithm processes $n$ entries in $O(n)$ time. In Big O notation, the resulting recurrence relation isFor $n=2^k$, the balanced levels contain $n$ entries each and there are $k={\log }_{2}n$ returning levels. Each costs $O(n)$, so the worst-case time complexity is $O(n\log n)$. For arbitrary $n$, there are at most $\lceil {\log }_{2}n\rceil$ returning levels, each processing at most $n$ entries, giving the same bound. The worst-case number of head comparisons is also $O(n\log n)$. Here ${\log }_2$ is the base-two logarithm. The MIT notes give this level-by-level analysis for merge sort.^[ref]

The conventional array implementation uses a reusable buffer of $n$ entries for the merge algorithm, together with $O(\log n)$ pending calls for recursion. Its auxiliary space complexity is therefore $O(n)$, beyond the original array. This bound describes that implementation. A linked list permits a merge algorithm that reconnects existing nodes; its storage accounting differs from copying array entries into a buffer.

For a short algorithm correctness outline, the empty and one-entry base cases are sorted. Assuming recursion correctly sorts both shorter halves, the merge algorithm returns all their entries in order. Equal keys within a half keep their relative order by the same argument applied to the smaller call; across halves, every left entry originally preceded every right entry, so taking left first preserves stable sorting. Both half-lengths decrease for $n\ge 2$, establishing termination.

First perform splaying on the key to be deleted, making its node the root of a tree. Delete that root, leaving left and right subtrees $L,R$. If either is empty, return the other. Otherwise find the maximum key $m$ of $L$ by following right-child references, and perform splaying on $m$ within $L$. This makes $m$ the root of $L$ with an empty right subtree. Attach $R$ there. The result is the original splay tree with exactly the selected key removed. An unsuccessful lookup leaves the represented set unchanged.

For algorithm correctness, all keys of $L$ are smaller than the deleted key, and all keys of $R$ are larger. Splaying preserves the binary search tree property by the permitted assumption. Since $m$ is the maximum of $L$, it has no larger key within $L$; since every key of $R$ exceeds $m$, attaching $R$ as its right subtree preserves every ordering condition. All remaining keys occur once. This is the join-based deletion of a splay tree.^[ref]

Root the tree arbitrarily. For each vertex $v$, let $D_1(v)$ be the minimum vertex cover size in its descendant subtree, conditional on selecting $v$, and $D_0(v)$ the corresponding minimum conditional on omitting $v$. Process the vertices in postorder traversal. For every child $u$ of $v$,At a leaf of a rooted tree, the empty sums give $D_1=1,D_0=0$. Return $\min \{D_0(r),D_1(r)\}$ at the root $r$.

For algorithm correctness, if $v$ is selected, each child subtree may independently use its cheaper state, since the connecting edge is already covered by $v$. If $v$ is omitted, each child must be selected to cover its connecting edge. Distinct child subtrees have no edges between them because the input is a tree. These observations prove the recurrences by structural induction. Each edge contributes constant work once, giving $O(|V|)$ time complexity and $O(|V|)$ space with adjacency lists. The single-vertex tree correctly has optimum zero. This is minimum vertex cover of a tree by dynamic programming.

A divide-and-conquer algorithm splits an instance into smaller instances of the same kind, solves them recursively, and combines their answers. The smaller instances should be sufficiently smaller to ensure algorithm termination; the combination cost determines whether splitting saves work. The two halves of merge sort illustrate this separation.

Dynamic programming identifies a collection of subproblems and dependencies among them, solves each distinct subproblem once, and stores its answer. A table in dependency order or memoization prevents repeated evaluation of overlapping subproblems. For optimization, an optimal substructure argument justifies constructing an optimal answer from optimal smaller answers.

A greedy algorithm repeatedly makes a locally best feasible choice and commits to it. It avoids exploring alternative continuations. Algorithm correctness therefore needs a greedy-choice property, often proved by replacing the first choice of an optimal solution with the greedy choice without worsening it.

Let $D[j]$ be the minimum number of jumps from index zero to index $j$, with $\infty$ denoting an unreachable position. The minimum forward-jump dynamic programming recurrence iswhere the minimum of an empty set is $\infty$ and $1+\infty =\infty$. Compute it in increasing index order:

D[0] = 0
for j = 1, ..., n-1:
    D[j] = INFINITY
    for i = 0, ..., j-1:
        if D[i] != INFINITY and A[i] >= j-i:
            D[j] = min(D[j], D[i] + 1)
return D[n-1]

For algorithm correctness, classify any route to $j>0$ by its penultimate index $i$. Every jump advances, so $i<j$, and legality requires $A[i]\ge j-i$. By the principle of optimality, a shortest prefix to $i$ can be used; this gives the lower bound represented by the recurrence. Conversely, a minimizing reachable predecessor supplies an actual route of length $D[i]+1$, proving attainability. Mathematical induction on $j$ therefore proves every stored value correct.

There are $n(n-1)/2$ predecessor tests, and two arrays are unnecessary when only the number is required. ThusFor the source example, the computed array isWhen $n=1$, zero jumps are needed even if the lone entry is zero. An unreachable final position returns $\infty$. Testing A[i] >= j-i also avoids forming a potentially overflowing sum i + A[i] in bounded implementations. A faster frontier-based algorithm is possible, but the displayed method directly supplies the requested dynamic programming solution.