Algorithm

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.

Generate every permutation of a finite list by recursively permuting its tail and inserting its head into each possible position. For $n$ distinct input elements, every shorter permutation has $n$ insertion positions, giving $n(n-1)!=n!$ results. Removing the distinguished head reconstructs the unique shorter permutation and insertion position.

In a Boolean matrix, find an axis-aligned rectangle containing only true entries and having maximum area. One approach first records each row's consecutive true run ending at each column. For each possible top-right corner, extend downwards, maintaining the minimum run width and maximizing height times width. This uses $O(N^3)$ time complexity on an $N$ by $N$ matrix after $O(N^2)$ preprocessing.

The number of consecutive true entries ending at a specified column of one row of a Boolean matrix. It is zero at a false entry and otherwise one plus the previous column's row run length, taking the value before column zero to be zero.

Studying an algorithm's resource use under a stated cost model. Time complexity, space complexity and amortized analysis answer different questions, so an operation count should specify the input-size parameter and what each primitive operation costs.

A method for proving that an algorithm must perform a certain amount of work: supply observations compatible with more than one possible input until enough information has been acquired to distinguish the required outputs. For exact membership in an arbitrary array, answering every inspected location with a value other than the target forces inspection of every location in the absent case, since any uninspected location could contain the target.

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.

Rearrange an array segment $a[l,r)$ into a low segment containing values below a pivot $p$ and a high segment containing values at least $p$, preserving the segment's multiset and leaving the rest of the array unchanged. The pivot need not itself occur, and either resulting segment may be empty.

An in-place scan maintains indices $l\le k\le j\le r$ with $a[l,k)<p$ and $a[k,j)\ge p$. A low value at $j$ is swapped into position $k$ and advances both indices; a high value advances only $j$. The unexamined length $r-j$ is a loop variant. At exit $j=r$, establishing the separation in $\Theta (r-l+1)$ time complexity and $O(1)$ auxiliary space complexity. Equal values consistently belong to the high side.

Maintain consecutive regions less than a saved pivot value, equal to it, unclassified, and greater than it. Compare the first unclassified entry: move a smaller one into the lower region, advance over an equal one, or exchange a greater one with the final unclassified entry. In the last case the incoming entry still needs classification. Each step shortens the unclassified interval by one. The final equality interval is nonempty when the pivot was selected from the input; Quickselect can discard that entire interval when searching another rank. Saving the value avoids accidentally comparing against a pivot index whose contents have moved.

A fair enumeration emits every required occurrence after finitely many computation steps. The inputs can be infinite; completeness does not mean waiting until they have all been exhausted. If two proper lazy lists alternate their next available entries, every occurrence reaches the output after finitely many swaps. In contrast, a nested list comprehension can remain forever in its first infinite inner list. Fairness concerns input occurrences, even when different occurrences happen to have equal values.

For an outer proper lazy list of inner proper lazy lists, introduce row $i$ in round $i$ and advance each active row once per round. Discard an active row when its terminating constructor is observed. Each round inspects finitely many rows, and the entry at row index $i$, within-row index $j$, is emitted in round $i+j$. Every earlier round has finite work, proving fair enumeration of all occurrences.

An implementation can keep a finite list of row remainders, append at most one newly introduced row, collect one head from every nonempty remainder, and retain their tails for the next round. It must not first combine all not-yet-introduced rows. In fact, foldr interleave [] ([1,2] : repeat []) can emit 1 and then block before 2; diagonal merging of lazy lists emits both. If infinitely many empty rows remain after the final output, detecting termination is impossible in general: the absence-detection obstruction for infinite lists prevents a universal promise of a terminating empty tail, while every required occurrence can still be emitted.

To find the order statistics at ranks $k,2k,\dots ,n$ when $n/k$ is a power of two, partition into equal lower and upper rank halves and recurse, stopping at blocks of size $k$. Return each leaf block's maximum. Half boundaries are multiples of $k$, so these leaf maxima are exactly the requested ranks. Linear-time selection gives total $\Theta (n)$ partition work per internal level and $\Theta (n)$ leaf work, hence $\Theta (n(1+\log (n/k)))$ overall. The shorter displayed bound applies when $n/k\ge 2$.

For deterministic linear-time selection, group keys into fives, compute the median of each group, and recursively select the median of those medians as a pivot. Apart from bounded end effects, at least $3n/10$ keys lie on either side. Thus the selection cost satisfies $T(n)\le T(\lceil n/5\rceil )+T(7n/10+O(1))+O(n)=O(n)$, since the fractions sum to $9/10<1$. A strong induction with sufficiently large linear coefficient absorbs the lower-order terms.

Find one specified order statistic without sorting every element. Partitioning about a pivot retains only the side containing the requested rank. Median of medians guarantees a balanced enough pivot to give worst-case linear time complexity.

Pair candidates from a totally ordered set and retain the greater one from each comparison until one winner remains. Every other candidate loses once, so $n-1$ key comparisons suffice to find the maximum of $n$ distinct values. A balanced tournament on $2^m$ inputs gives the winner $m$ direct losers. Retaining each loser's own defeat record preserves information for finding later order statistics. The comparison records form a rooted tree and are distinct from a graph-theoretic tournament, which includes a directed comparison between every pair.

After a balanced comparison tournament, the second-largest element is the maximum among the winner's $m$ direct losers. The third-largest must have lost directly to the winner or to that second-largest element: no smaller element could defeat it. Excluding the known top two leaves at most $(m-1)+(m-1)$ candidates, because the second-largest won at most $m-1$ earlier comparisons. The three stages use at most $(n-1)+(m-1)+(2m-3)$ key comparisons, proving the displayed bound. Defeat records must retain their earlier subtrees; keeping only the overall winner's direct-loser values discards information used by the last stage.

A selection algorithm that uses array partitioning around a pivot and recursively searches only the side containing the desired order statistic. If there are $s$ entries before the placed pivot, an earlier rank is unchanged and a later rank is reduced by $s+1$. Segment length strictly decreases, proving algorithm termination. The same reduction can update local bounds in a loop, using constant auxiliary space.

Balanced reductions give linear work by a geometric series, while repeatedly discarding only a constant number of entries can give quadratic work. For distinct entries and independent uniform random pivots, a pivot in the middle half has probability at least one half and reduces the retained length to at most three quarters, up to rounding. The expected number of attempts for each such reduction is bounded, so summing expected work over geometric size scales gives $O(n)$ expected time. This random-pivot guarantee is not a worst-case guarantee for a deterministic median-of-three heuristic. With duplicates and a strict two-way partition, random pivot choice alone can also fail to shrink an all-equal segment; a three-way partition treats equal keys together.

Choose the median value among the first, middle and last entries of an active array segment. For at least three distinct sampled values, the selected value cannot be the whole segment's minimum or maximum. It can still be the second-smallest or second-largest value, so a balanced split does not follow. Coincident sample indices in segments of length one or two can be handled by the same comparison code. Ties must also have a defined branch policy.

A distinct-input counterexample for Quickselect that chooses the first/middle/last median, reserves it at the last slot, scans lower values to the front, and finally swaps the pivot into place. Let $A_n$ be the following permutation of $0,\dots ,n-1$. For $n<4$, take increasing order. For $n\ge 4$, let $B=A_{n-2}+2$ componentwise and $m=\lfloor n/2\rfloor$, then setand put $A_n(j)=B(j-2)$ at every other index $2\le j\le n-2$. These assignments use every entry of $B$ once and add zero and one, so they really define a permutation.

The sampled values are $1,0,B(m-2)$, with the last at least two, so the pivot is one. After the initial pivot swap, the only lower value is the zero at index $m$. Moving it to the front places the displaced $B(m-2)$ at its intended tail position. The final pivot swap moves $B(n-3)$ from index one to the last position. Every other tail entry already has its intended position. Thus the complete partitioned result is exactly $[0,1]$ followed by $B$.

Selecting the maximum consequently repeats the same construction on $n-2$ entries. If $C(n)$ counts only pivot comparisons made by the partition scan, then $C(n)=n-1+C(n-2)$, with $C(1)=0$ and $C(2)=1$. Hence $C(n)=\lfloor n^2/4\rfloor$ and total runtime is $\Theta (n^2)$. For example, $A_6=[1,4,3,0,2,5]$. This disproves a linear worst-case claim even when every value is distinct.

To obtain the $k$-th smallest entry of two ascending sorted arrays of lengths $m,n$, choose prefix lengths $i,j$ with $i+j=k$. Search $\max (0,k-n)\le i\le \min (m,k)$ for the two boundary inequalities in the title, treating missing left boundaries as $-\infty$ and missing right boundaries as $+\infty$. Then all $k$ selected entries precede all unselected entries, so their largest boundary value is the answer. If $A_L>B_R$, decrease $i$; if $B_L>A_R$, increase $i$. These failures are monotone because one prefix grows as the other shrinks. Binary search thus takes $O(\log (\min (m,n)+1))$ comparisons when the shorter array supplies the searched prefix. Repeated values retain their multiplicities in the ranks.

Deciding whether $n$ open real intervals are pairwise disjoint has comparison complexity $\Theta (n\log n)$. Sort by left endpoint and scan the maximum previous right endpoint for the upper bound. For the lower bound, map integer keys $z_i$ to $(2z_i,2z_i+1)$. Such intervals intersect exactly when the original integers agree. Each comparison between endpoints $2z_i+a$ and $2z_j+b$, with $a,b\in \{0,1\}$, is determined by a comparison of $z_i,z_j$ and their fixed offsets, so the reduction preserves the comparison model. Apply the element distinctness problem lower bound.

Suppose a finite candidate set of size $N$ contains the truth, every query chooses a current candidate, and each wrong reply eliminates that candidate while retaining the truth. Then at most $N-1$ wrong queries occur. If a correct reply uniquely identifies the truth, an infinite strategy of this kind eventually repeats the true candidate; stopping when only one candidate remains takes at most $N-1$ replies. The proof is the strictly decreasing positive cardinality of the surviving candidate set after every nonidentifying round.

To score a guess against a fixed-length secret, first reserve every equal-position match. For the remaining positions, consume at most one unused secret occurrence for each cow. This two-stage rule prevents an earlier wrong-position token from using the occurrence needed for a later positional match. The sum of bull and cow counts is the multiset overlap of the two sequences. With only equality tests, deletion from a list gives a quadratic-time implementation; token-count maps can improve the allocation step when a suitable key representation is available.

A computational procedure using quantum state preparation, controlled operations and measurement, together with any required classical processing. Complexity counts the relevant operations and repetitions; a large superposition is not itself a guarantee of a useful speedup.

Approximate quantum counting estimates the number $k$ of satisfying assignments of a Boolean function, using a quantum oracle and quantum measurement. Controlled repetitions of a Grover search algorithm iteration let quantum interference reveal the count. For one input bit, a Hadamard test can give Pauli Z gate expectation value $1-k$: with the complemented phase oracle $U_f=\mathrm{diag}(2f(0)-1,2f(1)-1)$ and $G=-X{U}_f$, use $⟨+|X=⟨+|$ to obtain $⟨+|G|+⟩=-[(2f(0)-1)+(2f(1)-1)]/2=1-k$. Repeated preparations estimate this expectation value; one binary measurement result does not distinguish all three counts $0,1,2$.

The Bernstein-Vazirani algorithm identifies the coefficient string of a linear Boolean function with one Boolean quantum oracle call. It contrasts with the $n$ calls required by the classical query complexity of linear Boolean function identification. Prepare the data qubits at $|0{⟩}^{\otimes n}$ and an ancilla qubit at $|1⟩$, apply a Hadamard gate to every wire, query the function oracle, and apply the Hadamard gates again. The full output is $|a⟩|1⟩$.

The mechanism is Bernstein-Vazirani phase kickback. The Pauli X gate has eigenvector $|-⟩=(|0⟩-|1⟩)/\sqrt{2}$ with eigenvalue $-1$. Thus the target flips become relative quantum phases on the data, givingThe final Hadamard transform maps this product to $|a⟩$, so computational-basis measurement recovers every coefficient with certainty. The ancilla preparation for the Bernstein-Vazirani algorithm ensures the required minus sign, and the Hadamard-conjugated linear oracle gives an exact quantum circuit interpretation. One query is optimal for $n\ge 1$, since without a query the output cannot depend on the unknown string.

The displayed Bernstein-Vazirani algorithm prepares its ancilla qubit in the computational-basis state $|1⟩$ before the first Hadamard gate. At the function oracle it is therefore the $-1$ eigenstate $|-⟩$ of the Pauli X gate, which enables phase kickback. Preparing $|0⟩$ instead yields $|+⟩$ at the function oracle; target flips leave this state unchanged, so the data contain no information about $a$.

The Hadamard-conjugated linear oracle makes the more general statement transparent. With zero data and initial ancilla qubit $\alpha |0⟩+\beta |1⟩$, the full fixed quantum circuit outputsFor nonzero $a$, the correct data outcome has probability $|\beta {|}^2$. To obtain exact identification for all $a$, this preparation must have $\alpha =0$, so it is $|1⟩$ up to global phase. This is a condition on the prescribed preparation circuit: any alternative quantum state preparation that supplies $|-⟩$ at the function oracle is equivalent.

Let $U_a|x⟩|b⟩=|x⟩|b\oplus (a\cdot x)⟩$ be the Boolean quantum oracle for a linear Boolean function, and put $W=H^{\otimes (n+1)}$. The CNOT gates $C_{j\to y}^{a_j}$ implement $U_a$, where the data wires control the ancilla qubit. CNOT control reversal in the Hadamard basis and $W^2=I$ imply the exact unitary operator identityHere $\oplus$ on strings is bitwise exclusive or. To conjugate a product, insert $W^2=I$ between its factors; each factor reverses its control and target, and the unused Hadamard gates cancel. The global phase is exactly $1$. In particular, the identity holds on arbitrary quantum superpositions, not only on the initialized inputs of the Bernstein-Vazirani algorithm.

A heuristic algorithm uses a selective search or approximation to obtain a useful result efficiently, without a general guarantee of finding the exact optimum.

The extra working storage required by an algorithm, excluding the storage occupied by its input. This includes temporary tables and the stack of active recursive calls.

Rearranging a finite sequence according to a specified order while preserving its entries and their multiplicities. A sorting algorithm performs this operation; lexicographic order supplies a common order for tuples or strings.

Unification seeks substitutions for variables that make symbolic terms identical. First-order unification compares matching constructors recursively; an occurs check rejects substitutions that would make a variable contain itself.

First-order unification seeks substitutions making first-order terms identical. Constructor decomposition and the occurs check produce a most general unifier when one exists.

A most general unifier is a unifying substitution through which every other unifier factors by a further substitution. It records exactly the equality constraints forced by the terms.

The Bostan-Mori algorithm extracts a distant coefficient from a rational generating function $P(x)/Q(x)$ by multiplying both by $Q(-x)$. The new denominator is even; retaining the appropriate even or odd numerator coefficients halves the coefficient index at each step.

Bitwise AND combines binary representations position by position, setting a bit exactly when it is set in every operand. For bit masks representing sets, it computes intersection.

To discover a positive unknown integer $m$ by comparisons, test the thresholds $2^k,2^{2k},\dots$ for fixed $k\ge 1$. If the first threshold not smaller than $m$ has index $j$, fewer than $2^{kj}$ candidates remain and binary search needs at most $kj+O(1)$ comparisons. Since $j\le {\log }_2(m)/k+1$, the total is at most $(1+1/k){\log }_{2}m+O_k(1)$. Choosing $k\ge 1/ϵ$ makes the leading constant at most $1+ϵ$; the additive constant may depend on $ϵ$.

If $f(0)<0$ and $f(x)>0$ for all sufficiently large positive $x$, testing $1,2,4,\dots$ eventually finds a positive endpoint. Keep the previous nonpositive endpoint to obtain a bracket. If $t$ is the first successful exponent, there are $t+1$ endpoint tests. Subsequent sign-bracketing binary search in the last interval takes $t-1$ tests for $t\ge 1$, since its width is $2^{t-1}$. No monotonicity is needed, though intermediate sign crossings may be skipped. Fixed-width integer overflow and unreliable floating-point signs require explicit handling; eventual real positivity alone does not guarantee representable machine endpoints.

Coordinate compression replaces coordinates by a smaller representation while retaining the order or distance information needed by an algorithm. Rank compression retains only order; geometry-specific transformations may instead remove known gaps or widths.

The Aho-Corasick algorithm matches multiple patterns in a string using a trie equipped with failure links. After preprocessing the patterns, it scans the input while reporting every pattern ending at each position.

An Aho-Corasick automaton stores a trie of patterns together with failure links and pattern-output information. It supports simultaneous pattern matching by the Aho-Corasick algorithm.

The Tonelli-Shanks algorithm finds a square root of a quadratic residue modulo an odd prime. It uses the decomposition of the prime minus one into an odd part and a power of two to successively correct a candidate root.

A longest repeated substring is a maximum-length contiguous string occurring at two distinct starting positions in a text. The occurrences may overlap unless a nonoverlap constraint is explicitly imposed. It can be found by comparing all pairs of suffixes, or by taking the maximum longest-common-prefix length of adjacent entries of a suffix array. The latter characterization concerns correctness; the time needed to build the suffix array depends on the construction algorithm.

An FM-index is a compressed text index supporting backward search through the Burrows-Wheeler transform and occurrence counts. Character rank queries locate a matching interval; sampled suffix array positions then allow the actual text positions to be recovered. Query length, number of matches and the chosen sampling density control different parts of the search cost.^[ref]

Backward search finds a query's matching interval in a suffix array by processing the query from right to left. With inclusive one-based interval $[l,r]$, prepending $c$ changes it to $[C(c)+\mathrm{Occ}(c,l-1)+1,C(c)+\mathrm{Occ}(c,r)]$. An empty interval means no match. This works through the occurrence-order property of the last-to-first mapping.^[ref]

In a sorted cyclic rotation matrix, the last-to-first mapping sends the $k$th occurrence of a character in the last column to its $k$th occurrence in the first column. For one-based rows, $\mathrm{LF}(r)=C(L_r)+\mathrm{Occ}(L_r,r)$, where $C(c)$ counts smaller characters and $\mathrm{Occ}(c,r)$ counts $c$ in the first $r$ entries of the last column. It moves a rotation's start one character backwards cyclically. Equal characters retain the lexicographic order of their following sequences, which proves the occurrence-order rule.^[ref]

The Burrows-Wheeler transform appends a unique smallest terminator to a string, sorts its cyclic rotations in lexicographic order, and records the last column. It is reversible because the first and last columns contain the same characters and the last-to-first mapping preserves the occurrence order of each character. The resulting letter arrangement supports both compression and backward search.^[ref]

A transition to a shorter suffix match after an attempted extension fails. In a Knuth-Morris-Pratt automaton, the prefix function determines the next shorter matching prefix.

For a string $s$, the value ${\pi }_i$ is the length of the longest proper prefix of $s_0\cdots s_i$ that is also its suffix. Repeatedly following these lengths lists all proper borders of a string; this is the failure-link information used by the Knuth-Morris-Pratt algorithm.

An algorithm for enumerating polyominoes by maintaining included cells, an ordered frontier of untried cells, and excluded cells. Exploring inclusion and exclusion in a consistent order prevents different growth histories from counting the same rooted shape repeatedly.

Determine whether repeated deterministic updates revisit a state, and optionally find the preperiod and cycle length. Recording all visited states uses memory proportional to the visited orbit. Floyd's cycle-finding algorithm detects repetition with constant extra memory.

A constant-memory algorithm for detecting the eventual cycle in a sequence generated by repeated function evaluation. It holds a checkpoint fixed while a second pointer advances, doubling the checkpoint interval when exhausted; a second pass locates the start of the cycle.

For a deterministic iteration $x_{n+1}=f(x_n)$ on a finite set, move one pointer by one step and another by two steps. They eventually meet inside the repeated cycle. Restarting one pointer at the initial state and advancing both by one step locates the cycle entrance; a further traversal measures its length. The method uses constant extra space complexity and time proportional to the preperiod plus cycle length.

A family of algorithms that exploit monotonically changing geometric directions while traversing sorted points or the boundary of a convex polygon. For example, after sorting rays by polar angle around a point, a second index can advance monotonically to identify all rays lying in each open half-plane. Collinear rays require consistent boundary handling.

An algorithm that splits choices into two groups, enumerates partial results for each group, and matches compatible results. For $n$ binary choices, the two lists each have about $2^{n/2}$ entries instead of enumerating $2^n$ complete choices; the matching cost and memory requirements depend on the problem.

Given a finite sequence of real numbers, find a nonempty contiguous block with maximum sum. Its restriction to contiguous blocks distinguishes it from choosing an arbitrary subset. The problem admits a linear-time solution using Kadane's algorithm.

For a segment, store its total sum $S$, maximum possibly-empty prefix sum $P$, maximum possibly-empty suffix sum $Q$ and maximum possibly-empty internal contiguous sum $B$. Adjacent segment summaries combine byA prefix either stays on the left or includes the whole left segment and a right prefix. A suffix has the symmetric decomposition. An internal segment either stays in one child or crosses the boundary as a left suffix followed by a right prefix. These cases prove the formulas, including empty candidates. Store the corresponding endpoints to recover a winning segment. This constant-size summary gives a linear time divide-and-conquer algorithm for the empty-allowed maximum subarray problem.

For input $a_1,\dots ,a_n$, let $E_i$ be the largest sum of a nonempty contiguous block ending at $i$. The recurrence relation $E_1=a_1$ and $E_i=\max (a_i,E_{i-1}+a_i)$ is exact: an optimal block either starts at $i$ or extends an optimal block ending at $i-1$. The answer is ${\max }_i{E}_i$. Keeping only the current $E_i$ and best value gives linear time complexity and constant extra space complexity.

Iterative lengthening search repeatedly runs cost-bounded depth-first search, starting with threshold zero and replacing each unsuccessful threshold by the smallest rejected path cost. It uses a depth-first search stack rather than the potentially large search frontier of uniform-cost search.

Suppose an optimal plan has cost $C^{\ast }$ and each pass terminates. At every unsuccessful threshold $L<C^{\ast }$, some first rejected prefix of an optimal plan has path cost at most $C^{\ast }$. Therefore the next threshold is no larger than $C^{\ast }$. Any first returned goal state has cost at most $C^{\ast }$ and hence exactly $C^{\ast }$. Finite branching factor and a positive lower bound on step costs ensure that only finitely many search nodes precede that cost, giving completeness as well as optimality. With arbitrary real step costs, the threshold increments can be much smaller than the smallest step cost: the difference between two path costs need not itself be a step cost.

Search a matrix whose rows and columns are both nondecreasing by inspecting the top-right corner of the remaining rectangle. If that value is below the target, discard its row; if above, discard its column; if equal, return its coordinates. The loop invariant retains every possible match inside the rectangle. Each failure decreases its remaining height plus width by one, proving at most $n+m-1$ inspections for positive dimensions and constant auxiliary space. Row monotonicity alone is insufficient for the column exclusion.

A search algorithm whose OR nodes represent controllable choices and whose AND nodes require solutions for every possible outcome of a chosen action. In nondeterministic planning, a successful OR choice needs successful continuations for all its AND children. In contingent planning, those children can represent different observations and updated belief states. Cycle handling must match the required solution concept: ignoring a repeated state is not a proof that the goal will inevitably be reached.

Find two distinct input positions whose values sum to a target, or establish that no such pair exists. Distinct values are not required: two equal values may form a pair when they occur at different positions. On a sorted array, distinct-index two-sum by suffix lower bounds gives $O(N\log N)$ running time, while a two-pointer technique can give linear time.

A lower-bound search that probes two positions to retain one of three subintervals. For unresolved $[lo,hi)$ of positive length $d$, put $q=\lfloor d/3\rfloor$, $m_1=lo+q$ and $m_2=hi-1-q$. If $a(m_1)\ge x$, retain $[lo,m_1)$; if $a(m_2)<x$, retain $[m_2+1,hi)$; otherwise retain $[m_1+1,m_2)$. Sortedness preserves the lower-bound partition. The new interval lengths are $q,q,d-2q-2$, and the feasible middle case has nonnegative length at most $q$. This proves strict progress and $O(\log (N+1))$ comparison cost. Equality must retain the first possible boundary rather than return an arbitrary matching occurrence.

A search algorithm is optimal for a specified objective if its returned solution has the best objective value among all solutions. The objective is part of the claim: minimizing the number of actions does not generally maximize a reward assigned to terminal states. Breadth-first tree search optimizes total cost when all actions have the same positive cost.

A search algorithm is complete for a specified class of problems if it finds a solution whenever a solution exists in that class. This definition need not require termination on unsolvable instances; an additional termination guarantee should be stated separately. A finite branching factor makes breadth-first tree search complete for finite-depth solutions, while depth-first tree search additionally needs a reason it cannot be trapped on an infinite branch.

A search algorithm that explores action histories in a search tree. Two histories ending in the same state remain distinct nodes unless an additional repetition rule identifies them. Consequently a finite state space can generate an infinite search tree: a legal stay action at a nonterminal state already suffices. A graph search instead records explored states to control repetitions. Confusing these models changes termination and completeness claims.

Build a candidate incrementally, abandoning a partial candidate as soon as no valid completion is possible. A depth-first search explores one choice, restores the previous state, and tries the next. Constraint propagation and bounds can greatly reduce the visited state space, although the worst-case time complexity may remain exponential.

Suppose backtracking assigns each of finitely many variables once along each branch, branching only on distinct values in its initial nonempty constraint domain $D_i$. Then the number of leaves is at most ${\prod }_i|D_i|$, even if inconsistent partial assignments terminate early. Ignore constraints and associate a leaf with every full domain assignment extending its partial assignment. Each leaf has at least one such extension. Different leaves have disjoint extension families: at their first diverging choice they assigned different values to the same selected variable. These nonempty disjoint families lie in a Cartesian product of cardinality ${\prod }_i|D_i|$, proving the bound. The selected next variable can depend on the preceding assignments, provided each full assignment follows a unique branch.

The bound is exact for an unpruned enumeration tree, but need not be attained when actual constraints cause search pruning. Counting complete satisfying assignments alone also does not count failed partial leaves.

An algorithm that maintains information about a contiguous part of a sequence while moving its endpoints. Updating a fixed-length window sum needs subtraction of the outgoing term and addition of the incoming term. A window product can be updated by division only when the outgoing factor is nonzero; zero counts or zero-free segments handle that exception.

A search algorithm that tests candidates directly, without exploiting enough structure to avoid their enumeration. A small brute-force implementation is often useful for checking an optimized algorithm independently.

Discarding a branch of a search tree after proving that no completion can satisfy the constraints or improve the current best solution. For minimization, a lower bound on every completion justifies pruning when it is at least the best value already found; this is the principle behind branch and bound.

A number-theoretic sieve processes many integers together by marking or updating those sharing a divisor, rather than testing each integer independently. The sieve of Eratosthenes marks composite multiples of successive prime numbers; related sieves accumulate a smallest prime factor, Euler's totient function, or Möbius function for every argument up to a bound. The useful structure is that the multiples of a fixed integer form an arithmetic progression, so one loop can update all affected entries in an array.

For example, initializing an array to true and then marking $2p,3p,\dots$ for each surviving prime number $p$ leaves precisely the prime numbers unmarked, apart from the separately excluded zero and one. Every composite number has a prime factor, which proves that every composite is eventually removed. Starting the marking at $p^2$ avoids work already performed by smaller prime numbers. Different sieves use different update rules and time complexity bounds; the name alone does not imply the complexity of the sieve of Eratosthenes.

An odd-only sieve stores only odd candidates, handling the prime two separately. This reduces the candidate storage and avoids marking even composites repeatedly.

A totient sieve computes the Euler totient function for many integers at once. Initialize $\varphi (n)=n$ and, for each prime $p$, replace $\varphi (n)$ by $\varphi (n)(1-1/p)$ for every multiple $n$ of $p$.

A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.

Choose a modulus $W$ that is a product of small primes. Every prime not dividing $W$ must be coprime to $W$, so a search can restrict candidates to the corresponding residue classes modulo $W$. For several linear polynomials, discard each residue class in which any required value is divisible by a selected prime. The surviving residue classes can be combined using the Chinese remainder theorem.

A Du Jiao sieve computes a summatory arithmetic function using a Dirichlet convolution identity and memoization of repeated quotient arguments. For the Mertens function $M(n)={\sum }_{k\le n}\mu (k)$, the identity ${\sum }_{d\mid k}\mu (d)=[k=1]$ gives $M(n)=1-{\sum }_{i=2}^{n}M(\lfloor n/i\rfloor )$. Grouping equal quotients and precomputing small arguments makes this recurrence relation useful for large inputs.

A family of algorithms for summatory multiplicative functions that first computes suitable sums over primes at quotient values and then incorporates prime powers. The required prime-sum formulas and complexity depend on the particular multiplicative function.

A number-theoretic sieve that processes a large search range in smaller intervals. To find primes in $[L,H]$, first generate the primes at most $\sqrt{H}$, then mark their multiples in the current segment. Memory for the segment depends on its width rather than on $H$.

A number-theoretic sieve that visits each composite number exactly once, through its smallest prime factor. Keep a growing list of prime numbers; for each $i$, generate $ip$ only for stored primes $p\le \mathrm{spf}(i)$. Each composite $m$ has a unique representation $m=\mathrm{spf}(m)(m/\mathrm{spf}(m))$ admitted by this rule, giving $O(N)$ arithmetic updates up to $N$.

Given a fixed sequence of compatible matrices $A_1,\dots ,A_m$, choose a binary parenthesization of $A_1\cdots A_m$ that minimizes the number of scalar multiplications in ordinary matrix multiplication. The order of the matrices is fixed: parenthesization changes the grouping, not the operand order. Associativity preserves the product while intermediate matrix dimensions change the cost. The possible binary groupings are counted by the Catalan number $C_{m-1}$ for $m\ge 1$.

For matrix dimensions $r\times s$ and $s\times t$, ordinary matrix multiplication computes $rt$ matrix entries, each using $s$ scalar multiplications. Thus its cost is $rst$ scalar multiplications, with $rt(s-1)$ additions if each sum starts from its first term. Here we minimize only the scalar multiplication count, using this dense matrix multiplication rule throughout. The counts describe arithmetic operations, rather than measured elapsed time; matrix multiplication methods that exploit structure or use faster formulas require a different cost rule.

Take matrices $A$, $B$, $C$ with matrix dimensions $12\times 5$, $5\times 40$, $40\times 3$. Both groupings produce a $12\times 3$ matrix product, but their intermediate matrix dimensions differ:The second grouping first compresses $BC$ into a $5\times 3$ matrix, avoiding the $12\times 40$ intermediate matrix $AB$. The saving is $3060$ scalar multiplications, although both groupings use exactly two matrix multiplications. This is why counting only matrix multiplication operations hides the interesting choice.

Associativity permits these regroupings in exact arithmetic; commutativity is neither assumed nor generally true for matrix multiplication. Swapping $A$ and $B$ here would even make their matrix product undefined. In floating-point arithmetic, round-off error can make the two groupings yield different computed matrix entries; the cost optimum alone does not guarantee the smallest numerical error.