Codex @codex  0

Consider the nonstiff scalar initial value problem $y^{\prime }=-y$, $y(0)=1$, on $0\le t\le 8$. Its exact solution is the exponential decay $y(t)=e^{-t}$. Use step-doubling error estimation with the explicit Euler method: from the same numerical starting value $y_n$, form one coarse step $C_n$ and two half steps giving $F_n$:Accept $y_{n+1}=F_n$ when the absolute and relative error tolerances test $E_n=|{\hat{e}}_n|/s_n\le 1$ passes, with $s_n=10^{-5}+10^{-3}\max (|y_n|,|F_n|)$. There is no Richardson extrapolation in the accepted value. Both approximations have order of a numerical method one, while this local error estimator has step exponent $r=2$. Consequently the adaptive step-size controller uses a square root, not a cube root:Start with $h_0=1$. A rejected trial retains both $t_n$ and $y_n$, caps $q_n$ at one, and retries. A zero estimate uses $q_n=5$. Before every trial, cap $h_n$ at $8-t_n$. Stop with a failure if floating-point arithmetic gives $t_n+h_n=t_n$, or after 100000 trials. These rules specify the example completely; they are not a prescription for every ordinary differential equation solver.

The first two trials, $h=1$ and $h=0.2$, have $E\approx 247.525$ and $E\approx 9.90099$ and are rejected. The next trial has $h\approx 0.0572049$ and $E\approx 0.81$ and is accepted. For positive decreasing numerical values, $s_n=10^{-5}+10^{-3}{y}_n$, so the local error estimator givesWhen the relative term dominates, this suggests nearly constant accepted steps, approximately $2(0.9)\sqrt{10^{-3}}$. When $y_n$ falls below the crossover size $10^{-5}/10^{-3}=0.01$, the absolute term increasingly permits longer steps. The sharp final decrease in $h$ only lands on $t=8$; it does not indicate a sudden loss of smoothness.

The actual signed local defect from the same numerical input isHere $O$ is Big O notation, obtained from Taylor's theorem for the exponential function. Thus ${\hat{e}}_n$ agrees with the leading term as $h_n\to 0$, but is not identical to ${\ell }_n$. At $h=1$, $y_n=1$, the estimate is $0.25$ while the actual local defect is $e^{-1}-1/4\approx 0.117879$. Their closeness improves for the smaller accepted steps. Had we added ${\hat{e}}_n$ using Richardson extrapolation, the accepted formula would instead be $y_n(1-h_n+h_n^2/2)$, of order of a numerical method two; the same raw difference would still scale as $h_n^2$ and would not estimate that improved value's leading $h_n^3$ defect.

The global error $g_n=y_n-e^{-t_n}$ obeys an exact recurrence relation involving the actual local defects:Each previous global error contracts, yet the local defects keep adding. In the plotted run, 101 steps are accepted and two trials are rejected. Every accepted $E_n$ is at most approximately $0.81$, while the largest $|g_{n+1}|/s_n$ is approximately $38.6927$. At $t=8$, the numerical value is approximately $0.00027184218$, compared with the exact $e^{-8}\approx 0.00033546263$, giving absolute error approximately $6.36204\times 10^{-5}$. The right-hand plot deliberately scales actual global error by the same $s_n$ used for local acceptance; it is not a new global error tolerance test.

Tightening both absolute and relative error tolerances by a factor ten gives 315 accepted steps and endpoint absolute error approximately $2.14922\times 10^{-5}$; tightening both by a factor one hundred gives 991 accepted steps and endpoint absolute error approximately $6.94171\times 10^{-6}$. This is a convergence comparison for this particular initial value problem. The endpoint error decreases by about a factor three per tenfold tightening, rather than by ten: a first-order Euler method accumulates defects across many steps, while its local error estimator varies quadratically with $h$. A variable-step global ODE error bound needs propagation information as well as accepted local tests.

The absolute stability boundary remains a separate constraint. On the Dahlquist test equation $y^{\prime }=-\lambda y$ with $\lambda >0$, the accepted two-half-step formula has stability function $R(-\lambda h)=(1-\lambda h/2{)}^2$. It strictly damps perturbations only for $0<\lambda h<4$. Its local error estimator is ${\lambda }^2{h}^2{y}_n/4$, which can pass an absolute-tolerance test at tiny $y_n$ even outside this damping interval. In a stiff two-mode linear system, a fast mode can therefore constrain the step long after its visible amplitude has become small. An adaptive step-size controller does not turn an explicit Euler method into an A-stable method. Official solver documentation likewise distinguishes explicit Runge-Kutta methods for nonstiff problems from implicit Runge-Kutta methods and backward differentiation formulas for stiff equations.^[ref]

Write $n=|V|$ and $m=|E|$. Suppose each vertex identifier, list descriptor, link and optional edge weight occupies a constant number of machine words, and indexed array access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence adjacency lists use $O(n+m)$ machine words in Big O notation. A full adjacency matrix has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.^[ref]

Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full adjacency matrix entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A linked list also needs links; an array may have unused capacity. Storing only half of a symmetric matrix changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of machine words, their size must be included in the space complexity.

An unsorted adjacency list answers "does the edge $u\to v$ exist?" by linear search through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\ge 1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full adjacency matrix instead answers from its single $C,F$ entry in $O(1)$ time.^[ref]

Different promises change the query. A sorted array of neighbour identifiers permits binary search in $O(\log (d+1))$ time, but maintaining order after insertion may require shifting entries. A per-vertex hash table permits expected constant-time membership under the hashing and load assumptions of that data structure; it does not give that guarantee to an arbitrary adjacency list. A stored list length can likewise make a vertex degree query constant-time even though neighbour enumeration still has to visit its entries.

The advantage grows with scale. For a graph path on $n\ge 2$ vertices, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full adjacency matrix entries. Such a family is a sparse graph with $m=O(n)$. For a complete graph, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the adjacency list advantage in growth rate disappears. Choose by the workload: following existing edges favours adjacency lists; many arbitrary pair-membership queries can favour a full adjacency matrix. The representation organizes the same graph for different questions.

Amortized analysis bounds the total cost of every permitted sequence of operations from a specified initial state. An amortized $O(1)$ bound means that some constants $a,b$ satisfy ${\sum }_{i=1}^m{c}_i\le am+b$ for every such sequence of length $m$. The cost model and allowed operations are part of the claim; Big O notation alone does not specify them.

This distinction, and the credit and potential method viewpoints, are developed in R. Endre Tarjan's 1985 paper Amortized Computational Complexity, sections 1–2, pp. 306–308. The dynamic array doubling example below shows how an expensive operation can pay for itself through the cheap operations that precede it.

The direct divisor summatory function formula evaluates $N$ floor divisions. Its balanced Dirichlet hyperbola method formula evaluates $r=\lfloor \sqrt{N}\rfloor$ floor divisions and reuses their sum for the other strip, followed by doubling and square-overlap subtraction. Thus it uses $O(\sqrt{N})$ arithmetic operations, with big O notation, in a model that counts each division, addition and multiplication as one operation. At $N=10^6$, the division counts for these two formulas are $10^6$ and $10^3$.

For a general Dirichlet convolution, the asymmetric formula has $\lfloor A\rfloor +\lfloor B\rfloor$ outer terms; evaluating $F$ and $G$ has an additional cost. Under $AB=N$, equal thresholds minimize $A+B$, but an asymmetric split can be useful if the two partial sums have different evaluation costs. The balanced divisor summatory function gains the further reuse because its two arithmetic functions are identical.

These are arithmetic operation counts, rather than counts of elementary operations on binary digits: the integers grow with $N$, and division of longer integers costs more in that model of computational complexity theory. Computing $r$ also requires an exact integer square root, or checking and correcting a numerical square root until $r^2\le N<(r+1{)}^2$ holds.

A data structure storing entries at numbered positions, usually starting at index zero. The fixed-capacity representation considered here puts equal-sized slots consecutively in computer memory. The number $n$ of occupied slots can be smaller than the capacity; unused slots provide room for later entries. An array of references stores consecutive references, while the objects they identify can be elsewhere. ^[ref]

Let the first slot have abstract address $b$ and each slot occupy $s$ address units. Then indexed access computesFor toy values $b=100$, $s=4$, the slots for $A,B,C$ start at $100,104,108$; index $2$ goes directly to $C$ through $100+2\cdot 4=108$. These are illustrative slot addresses, not observed allocation addresses. Under the word-RAM (random-access machine) model for time complexity, word-sized arithmetic operations and any addressed computer memory access have constant cost, and the addresses and entries fit in words. Thus one array access takes $O(1)$ time in Big O notation, independently of the index. This is the access assumption needed by binary search. ^[ref]

Inserting $X$ after $B$ in an array holding $A,B,C$ with one unused slot produces $A,B,X,C$: first copy $C$ from slot $2$ to slot $3$, then write $X$ into slot $2$. Writing $X$ first would lose $C$ unless it had been saved separately. More generally, insert at index $i$ by copying occupied slots from right to left, then fill the gap; with spare capacity this moves $n-i$ entries and takes $O(1+n-i)$ time in Big O notation, so insertion near the middle has $O(n)$ time complexity. Removing an entry closes the gap by shifting later entries left. ^[ref]

A fixed-capacity array cannot accept another entry when full. A resizable representation can allocate a larger array and copy the entries. Doubling capacity when full gives $O(1)$ append cost by amortized analysis over a sequence starting empty, but a single append that copies $n$ entries still has $O(n)$ worst-case time complexity. The outline is a geometric series: copied capacities $1,2,4,\dots ,2^k$ sum to $2^{k+1}-1$, less than twice the number of appends that triggered the last copy. Middle insertion still pays for its shifts. ^[ref]

Asymptotic analysis describes what remains dominant as an argument approaches a specified limit. It compares functions or sequences by scale: how much of a complicated expression can be replaced by a simpler one, and how large is the omitted part? The limit may be $n\to \infty$ for a growing input or $h\to 0$ for a shrinking approximation parameter.

For example, $n^2+10^{5}n$ is eventually dominated by its quadratic term, since division by $n^2$ gives $1+10^5/n\to 1$. But at $n=100$, the linear term contributes $10^7$, compared with only $10^4$ from the quadratic term. A statement about the limiting scale and a good approximation at a particular input are different claims.

Three useful comparisons keep their strengths distinct. Big O notation supplies an eventual upper bound up to a constant multiplier; big theta notation supplies both an upper bound and a lower bound up to constants; asymptotic equivalence makes the ratio tend to one. Little o notation says that a term becomes negligible relative to a specified scale. These distinctions make approximations checkable instead of merely calling one expression small.

The same language connects time complexity with Taylor remainders. In an operation-count model, one asks how a cost scales with input size. In a Taylor expansion, one asks how the approximation error scales with the increment. Neither use requires interpreting the unspecified constant as one. The asymptotic comparison of exponential functions gives another example: dividing by the largest contributing exponential reveals the terms that disappear.

For functions with $g$ nonzero sufficiently near a specified limit,The same definition applies to sequences $a_n\sim b_n$ as $n\to \infty$. Equivalently, $(f-g)/g\to 0$: replacing $f$ by $g$ has a relative error tending to zero, and the difference is $o(g)$ in little o notation. The limit and reference scale are essential parts of the statement.

For example, $n^2+n\sim n^2$ because $(n^2+n)/n^2=1+1/n\to 1$. Replacing the former by the latter gives absolute error $n$, which grows without bound. Thus asymptotic equivalence controls a ratio, rather than requiring the absolute error to vanish. This distinction is crucial when approximating a rapidly growing factorial with Stirling's formula.

By contrast, $2n$ and $n$ have the same order in big theta notation, but are not asymptotically equivalent: their ratio remains two. For positive functions, asymptotic equivalence gives both-sided constant bounds eventually, whereas constant bounds alone do not recover the leading coefficient.

For a local example with real $h$, the exponential function obeys $e^h-1\sim h$ as $h\to 0$. The Taylor theorem with Lagrange remainder givesThus for $|h|\le 1$,This states $e^h-1=h+O(h^2)$ in big O notation, and division by $h$ shows that the relative difference measured against $h$ vanishes. The diagram uses positive $h$; the bound is valid on both sides of zero. At $h=0.1$, the absolute error is approximately $0.00517092$ and the relative difference against $h$ is approximately $0.0517092$.

The barycentric interpolation formula evaluates the same Lagrange polynomial using weights that depend only on the distinct interpolation nodes:At $x=x_i$, return $y_i$ directly, before dividing; the formula has removable singularities at the interpolation nodes. Multiplying every $w_i$ by the same nonzero constant leaves the answer unchanged. Driscoll and Braun derive this formula as a more efficient, numerically stable way to evaluate polynomial interpolation.^[ref]

For the interpolation nodes $0,1,2$, the weights are $(1/2,-1,1/2)$, or equivalently $(1,-2,1)$. With data $(1,2,5)$, at $x=1/2$ the denominator using the latter weights is $2+4-2/3=16/3$ and the numerator is $2+8-10/3=20/3$, giving $p_2(1/2)=5/4$ again. For eleven interpolation nodes in the Runge phenomenon figure, the generator computes the weights by the direct products above and returns stored values exactly at every interpolation node.

The direct products require $O(n^2)$ arithmetic operations once; each subsequent value uses $O(n)$ arithmetic operations. Here $O$ denotes Big O notation. At large polynomial degree or on poorly scaled intervals, forming these products can exceed the range of floating-point arithmetic; normalization or specialized weight formulas may be needed. Stable evaluation also cannot cure sensitivity intrinsic to the chosen interpolation nodes, measured by the Lebesgue constant of interpolation, or the approximation failure in the Runge phenomenon.

The Bellman-Ford algorithm solves the single-source shortest path problem in a finite directed graph with finite real edge weights, allowing negative weights. It repeatedly applies edge relaxation, so an improved tentative distance can improve its neighbours on a later visit. This makes it a label-correcting shortest-path algorithm.^[ref] If no negative-cost directed cycle is reachable from the source, at most $|V|-1$ complete passes suffice for all distances; a further check detects a reachable negative-cost directed cycle.^[ref]

There are two orientations to keep distinct. The usual single-source problem asks for distances from $s$, extending routes along outgoing directed edges. The Bellman inequalities above instead concern distances to a sink $r$, prepending incoming directed edges to known routes. The All-to-one Bellman-Ford recurrence below preserves that convention. Reversing every directed edge, with its weight unchanged, converts one problem into the other.

Here is an original single-source example with source $S$, vertex set $V=\{S,A,B,C,T\}$, and precisely these directed edges:The negative edge $A\to B$ is harmless: this directed graph has no directed cycle. Its best route to $T$ is $S\to A\to B\to C\to T$, of cost $4-2+3+2=7$. The other routes to $T$ cost $12$ through $S,A,T$ and $10$ through $S,B,C,T$.

Initialize $d(S)=0$ and the other tentative distances to $\infty$. In each pass apply single-source edge relaxation, $d(v)\leftarrow \min \{d(v),d(u)+w_{uv}\}$, scanning in the order $A\to T$, $C\to T$, $B\to C$, $A\to B$, $S\to B$, $S\to A$. Skip a candidate with $d(u)=\infty$. The figure records labels after each complete pass and uses current labels immediately: it is an in-place trace. In pass 2, $B\to C$ still uses $d(B)=5$, giving $8$; only later does $A\to B$ lower $B$ to $2$. Pass 3 carries that improvement to $C$, and pass 4 carries it to $T$. The final labels in order $(S,A,B,C,T)$ are $(0,4,2,5,7)$; the final shortest-path predecessors are $S,A,B,C$ for $A,B,C,T$ respectively.

The scan order explains the delay. Scanning instead as $S\to A$, $S\to B$, $A\to B$, $B\to C$, $C\to T$, $A\to T$ gives those same final labels in just one in-place pass. The Synchronous Bellman-Ford recurrence has a precise bound on the number of edges used by a recorded route; an in-place pass can propagate along several edges and need not have that interpretation. Both implementations have the $|V|-1$ pass guarantee under the stated no-reachable-negative-cycle hypothesis.

With a stored list of edges, complete-pass Bellman-Ford algorithm has time complexity $O(|V||E|+|V|)$ and uses $O(|V|)$ extra space for labels and shortest-path predecessors, using Big O notation and constant-cost arithmetic. The extra $|V|$ accounts for initialization even when $E$ is empty. A pass with no strict decrease permits early termination. A queue variant instead revisits outgoing edges of vertices whose labels improved; the authored implementation provides this alternative and has $O(|V||E|)$ worst-case running time on its usual nontrivial instances.^[ref] For nonnegative weights, the Dijkstra algorithm and its existing distance-frontier figure explain how permanent labels can avoid these repeated passes; the existing edge relaxation figure illustrates one update at a time.

For real-valued functions on the natural numbers, $f(n)=\Omega (g(n))$ means that constants $c>0$ and $N$ satisfy $|f(n)|\ge c|g(n)|$ for every $n\ge N$. This is an eventual lower bound on magnitude. In algorithm analysis the functions are usually nonnegative, so the absolute values can be omitted. Together with the upper bound of big O notation, it gives big theta notation. This is the algorithmic lower-bound convention for $\Omega$, rather than a convention expressing only a positive limit superior along a subsequence.

At the specified limit, big theta notation means that two positive constants give both-sided bounds:sufficiently near the limit. Equivalently, $f=O(g)$ and $g=O(f)$ in big O notation. In operation-count analysis, $3n^2+7n+4=\Theta (n^2)$ for $n\ge 1$, using $c=3$ and $C=14$. This supplies a tight scale without asserting that the normalized ratio tends to one.

For an example with no limiting ratio, let $f(n)=n(2+(-1{)}^n)$ for positive integers $n$. Then $n\le f(n)\le 3n$, so $f(n)=\Theta (n)$, but $f(n)/n$ alternates between one and three. A tight growth order is therefore weaker than asymptotic equivalence. The constant bounds also do not fix an exact factor by which a function changes when its argument doubles.

Donald E. Knuth's 1976 paper proposes using $\Theta$ for two-sided constant bounds in algorithm analysis. He credits Bob Tarjan and Mike Paterson with independently suggesting the notation. His discussion gives a concrete motivation for distinguishing an eventual upper estimate from a tight comparison. ^[ref]

A binary heap represents a priority queue as a complete binary tree obeying a heap order. We use the minimum convention: the priority of every parent in a rooted tree is no greater than the priorities of its children in a rooted tree. Equal priorities are allowed. Each stored entry may be a record carrying a priority key; the numerical example below displays only keys. Reversing the inequalities gives the maximum convention.

The complete binary tree can be stored directly in a zero-indexed array $A=(A_0,\dots ,A_{n-1})$: read its levels from top to bottom, left to right. The root of a tree is at index $0$. The possible children in a rooted tree of index $i$ are at $2i+1$ and $2i+2$, and an index denotes a present entry only when it is less than $n$. For $i>0$, its parent in a rooted tree is at $\lfloor (i-1)/2\rfloor$, using the floor function. Thus the links of the complete binary tree are determined by arithmetic rather than separately stored pointers.

ConsiderThe children in a rooted tree of index $0$ have keys $5,3$; those of index $1$ have keys $9,7$; those of index $2$ have keys $8,4$. The six comparisons $2\le 5$, $2\le 3$, $5\le 9$, $5\le 7$, $3\le 8$, $3\le 4$ establish the heap order. At index $4$, the parent in a rooted tree is index $\lfloor (4-1)/2\rfloor =1$, carrying key $5$.

The array is visibly not a sorted array: $5$ precedes $3$, and $8$ precedes $4$. Nor is the last entry a maximum: it is $4$, whereas the maximum is $9$ at index $3$. The heap order compares ancestors and descendants, without imposing an order between separate branches. Nevertheless, following the graph path from the root of a tree to any entry gives a chain of nondecreasing priorities. This short argument proves that peek can return $A_0$, a minimum, without inspecting the other entries.

Insertion appends an entry to the array, preserving the shape of the complete binary tree, then uses sift up to repair the heap order. Insert key $1$ into the displayed binary heap. It is appended at index $7$, and exchanges with indices $3$, $1$, then $0$:The moving key follows $7\to 3\to 1\to 0$; the keys $9,5,2$ each move down one level. Only this chain needs repair.

Now apply extract-min. Save key $1$, move the last key $9$ to the root of a tree, and shorten the array to length $7$. Use sift down, always choosing the smaller of the present children in a rooted tree:First $9$ exchanges with key $2$ at index $1$, since $2<3$; then with key $5$ at index $3$, since $5<7$. At index $3$, the possible children in a rooted tree would be indices $7,8$, both outside the shortened array, so the process stops. The returned key is $1$, and the remaining binary heap is exactly the original one.

For a nonempty binary heap with $n$ entries, the deepest level is $\lfloor {\log }_{2}n\rfloor$, using the floor function and logarithm. Each exchange moves one level and uses only a bounded number of comparisons. The resulting time complexity bounds, expressed in Big O notation, are:

These bounds assume constant-cost indexed access, key comparisons and exchanges, and available array capacity for insertion. Allocating and copying a larger array is a separate cost. Empty and one-entry cases take constant work.

To build a binary heap, begin at index $\lfloor n/2\rfloor -1$ and work backwards. Entries without children in a rooted tree already obey the heap order. Each sift down, also called heapify down, starts with every present smaller rooted tree below it already repaired. Most entries are close to the bottom and can move very little; successively longer repair distances occur for geometrically fewer entries. Summing these distances gives $O(n)$ work, rather than charging $O(\log n)$ to every entry. MIT's notes give this bottom-up construction and contrast it with repeated insertion.^[ref]

The Dijkstra algorithm additionally needs to decrease the priority of an existing vertex when its tentative distance improves. Given its current index, lowering the key followed by sift up takes $O(\log n)$ time for $n\ge 2$. An indexed binary heap maintains a separate map from item identity to its current index and updates that map after every exchange. For vertices numbered in a fixed range, the map can be another array, giving constant-time index lookup. An ordinary unindexed binary heap supplies no such guarantee: locating an arbitrary item can require scanning $n$ entries. Item identity and priority must remain distinct, especially when several vertices have equal tentative distances.

The attractive compromise is local organization with global usefulness. A binary heap maintains only the heap order, yet every extract-min gives the next smallest key. Repeated extraction of the original example gives $2,3,4,5,7,8,9$, so a priority queue also supplies a sorting algorithm without storing a sorted array between extractions.

For the optimized left-to-right exponentiation by squaring algorithm, let $\ell =\lfloor {\log }_{2}n\rfloor +1$ be the length of the binary expansion of a positive integer $n$, and let $w=\mathrm{wt}(n)$ be its Hamming weight, the number of digits equal to one. There are exactly $\ell -1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count isHere $S$ counts squarings and $T$ counts further multiplications by the base; every squaring counts as one multiplication in $C$. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero multiplications; define $C(0)=0$ separately.

For a fixed length $\ell$, the bounds are $\ell -1\le C(n)\le 2\ell -2$. A power of two reaches the lower bound because its Hamming weight is one; $n=2^{\ell }-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell =4$ and $w=3$, giving $C(13)=5$. Thus the arithmetic operation count is $O(\log (n+1))$ in Big O notation, but inputs of similar magnitude can have different counts.

This is a count for the specified algorithm, not a claim that it always minimizes multiplications among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five multiplications: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.

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

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

A bounding volume hierarchy is a data structure arranged as a rooted tree: leaves store objects, and each internal node stores a bounding volume enclosing its children in a rooted tree. Consequently, every node encloses all objects in its subtree. A common choice is a binary tree of axis-aligned bounding boxes. The objects assigned to sibling subtrees can be different even when their bounding volumes overlap.^[ref]

Here is an exact two-dimensional example. Use the triangles $A,B$ from bounding volume, together with $C$ having vertices of a polygon $(6,0),(8,0),(6,2)$ and $D$ having vertices of a polygon $(6,3),(8,3),(8,5)$. Group $A,B$ under $L$, and $C,D$ under $R$. Their parent axis-aligned bounding boxes and the box at the root of a tree areThe diagram shows all seven nodes. Taking the coordinate-wise minimum and maximum of the two child boxes constructs each parent box; the resulting box contains the set union of the children, and can also contain empty space between them.

A bounding volume hierarchy traversal starts at the root of a tree and discards a subtree when its bounding volume misses the query. Accepted internal nodes expose their children; accepted leaves supply candidates for actual shape tests. Box2D's official Collision: Dynamic Tree describes axis-aligned bounding box region queries that return overlapping leaf boxes. A query box that bounds a different query shape can produce additional false candidates.

For the closed query rectangleleft-first depth-first search tests the node boxes in order: root, $L$, $A$, $B$, $R$. The first four overlap $Q$; $R$ does not, because its smallest $x$-coordinate is $6>9/5$. Pruning $R$ skips both $C$ and $D$. Five box tests leave two broad phase candidates. The narrow phase rejects $A$, since $x+y\ge 16/5>2$ throughout $Q$, and accepts $B$: the point $(7/4,13/8)$ belongs to both $Q$ and $B$. There are two detailed shape tests and one true hit.

For a query asking for all intersections, time complexity depends on the number $v$ of visited nodes and the cost $T_j$ of each candidate shape test. With fixed dimension and constant bookkeeping cost per node, the work iswhere $c$ counts candidate objects and $O$ is Big O notation. A balanced binary tree has small height of a binary tree, but a query can enter both children at every level. In this example a query containing $[0,8]\times [0,5]$ visits all seven nodes and tests all four triangles. More generally, a full binary tree with $n$ single-object leaves has $2n-1$ nodes, so such a query takes $O(n)$ work for constant-cost shape tests even when its height of a binary tree is $O(\log n)$. Listing $n$ hits itself requires $n$ outputs. Small height alone gives no unconditional logarithmic query bound.

For collision detection between two bounding volume hierarchies, traverse pairs of nodes: reject disjoint pairs of bounding volumes, expand a nonleaf member of an accepted pair, and apply the narrow phase at accepted leaf pairs. A single collection's self-query must exclude pairing an object with itself and avoid duplicate unordered pairs. If every object overlaps every other object, reporting all pairs already requires $n(n-1)/2$ results. Construction quality, empty space in boxes and the queries determine how much pruning is useful.^[ref]

For a short correctness outline, an object is enclosed by its leaf box, and each child box is enclosed by its parent box. Repeated subset relations carry this property to every ancestor. A true query intersection therefore prevents rejection at every ancestor of the object's leaf. Updating leaf boxes after motion also requires restoring all affected ancestor bounds before querying.

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

A numerical value retained for reuse by memoization. It is usable only while the spreadsheet formula and all its relevant inputs remain valid. After changing A1 from 3 to 5, following outgoing directed edges finds exactly B1,B2,C1,D1. Invalidate their cached cell values before evaluating another requested result; install the new input value for A1. The cached cell values of A2 and E1 remain valid because neither has a directed path from A1.

One recomputation in the restricted topological order B1,B2,C1,D1 gives $9,10,19,19/2$. Four spreadsheet formulas are recomputed, while E1 stays at 16. Removing invalid values from the cache prevents a subtle error: a finished marker from the previous evaluation does not prove that the old value is correct after an edit. The affected set is conservative; a changed prerequisite might leave a consumer's value numerically equal, but this simple scheme still invalidates it. For a formula edit, update the incoming directed edges and corresponding outgoing consumer lists as well as invalidating the edited spreadsheet cell and its downstream consumers. Microsoft's documentation explicitly describes both direct and indirect dependents being marked for recalculation.^[ref]

For demand-driven evaluation, memoization combines with depth-first search. Each spreadsheet cell has one of three states: UNSEEN means no valid cached cell value; ACTIVE means its evaluation is on the current call stack; FINISHED means a valid value is available. Initialize valid input spreadsheet cells as FINISHED. Start with all spreadsheet formulas UNSEEN, or retain only valid FINISHED entries after invalidation. The following original algorithm uses an ordered references list and an apply_formula operation for each spreadsheet formula:

def value(cell):
    if state[cell] == FINISHED:
        return cache[cell]
    if state[cell] == ACTIVE:
        i = stack.index(cell)
        raise CircularReference(stack[i:] + [cell])
    state[cell] = ACTIVE
    stack.append(cell)
    try:
        args = [value(p) for p in references[cell]]
        cache[cell] = apply_formula(cell, args)
        state[cell] = FINISHED
        return cache[cell]
    except Exception:
        state[cell] = UNSEEN
        raise
    finally:
        stack.pop()

Requesting D1 first makes D1,C1,B1 active, then reads the finished inputs A1,A2. B1 finishes at 7. Evaluating B2 reuses the finished value of A1 and finishes at 6; C1 finishes at 13 and D1 at $13/2$. A later request for D1 immediately returns its cached cell value. The shared prerequisite A1 is not a directed cycle: it was finished before the second request. The crucial distinction is between a previously visited vertex and a still-active vertex. The exceptional path restores unfinished states while unwinding the call stack, so failed evaluations are not cached as successful results. MIT's depth-first search notes use stack-duration marks to distinguish an edge to an active ancestor and to detect a directed cycle.^[ref]

With adjacency lists and constant-time state/cache access, the structural work of a successful demand-driven evaluation is $O(|V_R|+|E_R|)$ in big O notation, where $V_R$ and $E_R$ are the requested spreadsheet cells and their recursively reached prerequisites and references. Each reached spreadsheet formula is computed once; each reference is inspected once. This time complexity counts dependency bookkeeping separately from the cost of the arithmetic operations. Detecting a spreadsheet circular reference can additionally scan the current call stack once to report its witness.

With storage allocated in advance, each successful insertion, removal, peek, size, and full/empty check uses $O(1)$ worst-case time complexity in Big O notation. This assumes constant-cost indexed array access, bounded machine word index arithmetic and fixed-cost scalar item reads and writes. Each operation touches a bounded number of slots and fields regardless of $n$ and $C$; no shifting, scanning or resizing occurs. Rejected operations also take constant work. Producing a copy of all $n$ live items takes $O(n)$ work under the same scalar-cost assumptions.

The preallocated array occupies $O(C)$ scalar slots plus constant bookkeeping. Allocation and any initial slot construction are separate setup costs. Copying a large item, running an expensive destructor or callback, allocating an item, or growing a dynamic array changes the operation cost and must be charged separately. The bound is worst-case structural work, with no need for amortized analysis, and says nothing about a measured wall-clock deadline.

These formulas describe sequential calls. Wrapping array indices implies neither atomic operations nor safe access from multiple software threads. Publication of an item's contents and reuse of its slot require a protocol justified under the relevant memory model, including any necessary acquire-release synchronization. The kernel documentation discusses barriers under explicit producer/consumer restrictions; Boost's documentation separately requires mutual exclusion for shared access involving writes. Neither property follows merely from choosing a circular buffer.^[ref][ref]

Apply the midpoint quadrature rule on each of $n$ equal panels of a partition of an interval, with $h=(b-a)/n$:Each quadrature node is a panel midpoint and each quadrature weight is $h$. For $f\in C^2[a,b]$, put $K={\max }_{x\in [a,b]}|f^{\prime \prime }(x)|$. Summing the panel quadrature errors givesfor some $\xi \in (a,b)$. Each panel contributes at most $K{h}^3/24$; there are $n=(b-a)/h$ panels, explaining the composite midpoint rule error of order $O(h^2)$ in big O notation. On a nonuniform partition of an interval with panel widths $h_j$ and largest width $H$, the corresponding bound is $K{\sum }_j{h}_j^3/24\le K(b-a)H^2/24$.

For $f(x)=x^2$ on $[0,1]$, summing the sampled polynomial exactly yieldsDoubling $n$ divides the absolute error by exactly four. For a general $C^2$ function, halving $h$ divides the displayed error bound by four, but the actual absolute error need not follow that ratio: cancellation can make it smaller or zero. Continuous functions still give convergence as the largest panel width tends to zero, by uniform continuity; without the bounded second derivative, the second-order rate is not guaranteed. Noise sensitivity of a quadrature rule explains a separate limitation when samples are inexact.