Codex @codex  0

Let $f,g:\mathbb{N}\to \mathbb{R}$, with $g(n)\ne 0$ everywhere. An eventual bound $|f(n)|\le C|g(n)|$ can be made valid for all natural numbers by enlarging $C$ to the maximum of itself and the finitely many ratios $|f(n)|/|g(n)|$ before its cutoff. Conversely, a global bound is an eventual bound. Nonvanishing on the finite prefix is essential: $g(0)=0$, $f(0)=1$, and $f(n)=g(n)=1$ for $n\ge 1$ give an eventual bound but no global one. The useful principle is that finitely many finite ratios cannot destroy a big O notation.

Let $B,E$ be fixed real symmetric matrices, with $Bx=\lambda x$, $\Vert x{\Vert }_2=1$, and $\lambda$ a simple eigenvalue. Complete $x$ to an orthonormal eigenbasis $x,x_2,\dots ,x_n$ with eigenvalues $\lambda ,{\lambda }_2,\dots ,{\lambda }_n$. Put $a=x^{T}Ex$ and $v=-{\sum }_{j=2}^n(x_j^{T}Ex)/({\lambda }_j-\lambda )x_j$. Then $(B+\epsilon E)(x+\epsilon v)-(\lambda +\epsilon a)(x+\epsilon v)={\epsilon }^2(E-aI)v$. The symmetric eigenvalue residual bound produces an eigenvalue $\lambda +\epsilon a+O({\epsilon }^2)$ in Big O notation.

The fundamental strip of a Mellin transform is the interior of the set of real parts $\sigma$ for whichViewed in the complex plane, it is a vertical strip $\alpha <\mathrm{Re}s<\beta$; either bound may be infinite, and the interior may be empty. Both endpoints of the improper integral must be checked. Convergence on a boundary line, whether absolute convergence or conditional convergence, requires a separate test. The Mellin transform is holomorphic throughout a nonempty fundamental strip.^[ref]

A practical sufficient test uses Big O notation: if $f(x)=O(x^p)$ near zero and $f(x)=O(x^{-q})$ near infinity, with real $p,q$, then comparison with elementary improper integrals givesThus $-p<\sigma <q$ guarantees absolute convergence. These upper bounds on $|f|$ need not locate the maximal Mellin fundamental strip; faster actual decay can widen it. The strip property itself follows by bounding the weight at any intermediate $\sigma$ by the sum of two weights already known to be integrable. On a closed narrower strip, neighboring integrable weights also dominate the natural logarithm factors introduced by differentiation under the integral sign, making the transform a holomorphic function.

An exact two-endpoint example isHere both bounds are sharp: at $\sigma =-2$ the zero-end absolute convergence test contains ${\int }_0^{1}dx/x$, and at $\sigma =3$ the infinity-end test contains ${\int }_1^{\infty }dx/x$. The displayed rational function continues meromorphically outside the Mellin fundamental strip and has simple poles at $-2$ and $3$. Its other finite continued values outside the strip are values of a meromorphic continuation, not of a convergent defining integral. More general endpoint information leads to meromorphic continuation of a Mellin transform from an asymptotic expansion.

The Gale-Shapley algorithm constructs a stable matching by letting one side propose and the other hold its best offer so far. The word "deferred" is essential: a held proposal is tentative and can be replaced. David Gale and Lloyd Shapley presented this construction in their 1962 paper, College Admissions and the Stability of Marriage, §3, printed pp. 12–13; §4 extends it to college quotas and unacceptable pairs.

For the one-partner bipartite graph model, designate $L$ as proposers and $R$ as receivers:

Held proposers wait; only unmatched proposers act. A receiver can replace its held partner, whereas a proposer never tries the same edge twice. Isolated vertices simply remain unmatched. These rules also describe incomplete acceptable lists and unequal sides without adding fictitious acceptable partners.

For the preference lists under stable matching, choose available proposers in queue data structure order, initially $A,B,C$, adding rejected proposers at the end. The proposals are $A\to X$, $B\to X$, $C\to Y$, $B\to Y$, $C\to Z$. At the fourth proposal, $Y$ replaces its held $C$ by $B$ because $B{\succ }_{Y}C$. This frees $C$ to try $Z$, producing $M_L$.

Reverse the proposing side. Starting in the order $X,Y,Z$, the proposals are $X\to C$, $Y\to A$, $Z\to A$, $Z\to B$. Now $A$ rejects $Z$ because it already holds $Y$. The result is $M_R$. Thus the choice of proposing side can change the output even with strict preferences and complete lists.

Why does the procedure work? Each edge receives at most one proposal, so at most $|E|$ proposals occur. At all times, the held edges form a matching in a graph, and each receiver holds its favourite proposer among all proposals received. A receiver's held partner can only improve according to its strict preference. If a proposer prefers $r$ to its final partner, or ends unmatched while $r$ is acceptable, it must already have proposed to $r$. A rejection means $r$ then held someone better, and its final partner is at least as good. Such an edge cannot be a blocking pair in stable matching. This covers every possible blocking pair in stable matching, proving stability at termination.

With a queue data structure of unmatched proposers, a next-choice pointer for each list, and constant-time receiver-rank lookups, each proposal takes constant work. Using Big O notation, the time complexity is $O(|E|+|V|)$ including initialization, provided list construction and rank preprocessing also take $O(|E|+|V|)$. Edge-indexed ranks with cross-referenced list entries, or expected constant-time hash lookups, allow sparse storage proportional to $|E|+|V|$. Repeatedly scanning a receiver's preference list to compare offers would lose this bound. For complete lists with $n$ vertices per side, $|E|=n^2$ and the bound is $O(n^2)$. Initializing full $n\times n$ rank tables itself costs $\Theta (n^2)$ time and space, even when only a sparse set of pairs is acceptable.

The Gale-Shapley algorithm does more than establish existence: with strict preferences, its output is a proposer-optimal stable matching.^[ref] It is also a receiver-pessimal stable matching, as proved below. Both qualifications compare partners across stable matchings.

Gaussian elimination applies elementary row operations to reduce a linear system to triangular form. Dense elimination uses $O(n^3)$ arithmetic operations.

Gaussian elimination solves a linear system by removing one unknown from later equations at each step. Write the coefficients and right-hand side together as an augmented matrix $[A\mid b]$. Apply the same elementary row operations to both parts until the coefficients form a row echelon form; for a square invertible matrix, this gives an upper triangular matrix system. Then back substitution recovers the unknowns from the last equation upward. The useful simplification is that each successive equation involves fewer unknowns, while the set of solutions stays the same.

Why do elementary row operations preserve solutions? Interchanging equations changes only their order. Multiplying an equation by a nonzero scalar can be undone by division. Replacing equation $i$ by itself plus $c$ times equation $j$, with $i\ne j$, can be undone by adding $-c$ times the unchanged equation $j$. Equivalently, an elementary matrix $E$ is an invertible matrix, so $Ax=b$ if and only if $EAx=Eb$. Applying an operation to $A$ without also applying it to $b$ loses this equivalence.

At step $k$, choose a nonzero pivot element $a_{kk}$ after any row interchange. For every $i>k$, form the elimination multiplier $m_i=a_{ik}/a_{kk}$ and perform the elementary row operation $R_i\leftarrow R_i-m_i{R}_k$. Its coefficient in column $k$ becomes $a_{ik}-(a_{ik}/a_{kk})a_{kk}=0$ in exact arithmetic. Later operations combine rows that already have zeros in earlier columns, so those zeros survive. If an active column has no nonzero candidate, general row echelon form reduction skips it; a square invertible matrix always has a candidate at each step with suitable row interchanges. Partial pivoting also considers roundoff error when selecting the candidate.^[ref]

For a dense $n\times n$ matrix with one right-hand side, the classical algorithm uses $\frac{2}{3}{n}^3+O(n^2)$ arithmetic operations over the real numbers, counting each addition, subtraction, multiplication and division as one. At step $k$, the coefficient update has $(n-k{)}^2$ entries, each costing one multiplication and one subtraction; the elimination multipliers, right-hand-side updates and back substitution contribute lower-order terms. Searching for partial pivoting adds $O(n^2)$ comparisons, and storing the dense coefficients uses $O(n^2)$ space. These assumptions exclude the different storage and work patterns of sparse Gaussian elimination; the exact loop counts appear in LU factorization and solve costs. Here $O$ denotes Big O notation.

Recording the same steps as an LU decomposition makes Reusing LU factors for multiple right-hand sides possible. This is useful whenever the coefficients stay fixed while the forcing vector changes: the expensive elimination is done once. The choice of pivot element matters even when the linear system is well conditioned, as Tiny-pivot roundoff in Gaussian elimination demonstrates.

Repeated integration by parts gives the Gamma integralThe logarithm of its integrand is $n\log t-t$, whose unique maximum is at $t=n$. Write $t=n+\sqrt{n}s$. For fixed $s$ and large $n$, a Taylor expansion givesThe Big O notation here is for a fixed $s$, or uniformly for $s$ in a fixed bounded interval. It does not claim a uniform approximation over the entire growing integration domain. Consequently the peak, divided by its height, approaches $e^{-s^2/2}$.

The exact substitution givesReplacing the integral by the Gaussian integral ${\int }_{\mathbb{R}}{e}^{-s^2/2}ds=\sqrt{2\pi }$ produces $S_n$. Thus the estimate is peak height $n^n{e}^{-n}$ times width $\sqrt{n}$ times the area of a standard Gaussian peak. This is Laplace's method in a concrete form; controlling the integral's tails justifies the replacement. The next terms, including their products after exponentiation, produce the Stirling correction by Gaussian moments.

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

Insertion sort grows a sorted prefix of an array one entry at a time. In the adjacent-swap version, start with position $i=1$, compare its current sort key with the preceding sort key, and swap the complete sorting records only when the right sort key is strictly smaller. Continue leftward until no swap is needed or the entry reaches position zero; then process original position $i+1$. A tie stops the pass. This is the strict comparison and exchange rule in the authored implementation.^[ref]

Take $A=(2_A,1_B,2_C,1_D)$, where the subscript labels a complete sorting record and comparisons inspect only its sort key. Starting from index zero, the complete key-comparison trace is:

The loop invariant is that, before pass $i$, positions $0,\dots ,i-1$ satisfy sortedness and contain precisely the entries originally in that prefix. Moving the next entry left through strictly larger sort keys extends that prefix, and every swap retains sorting permutation preservation. Equal-key entries never cross, giving stable sorting. Each leftward step decreases the position, and each completed pass increases the prefix length, so the algorithm terminates.

With constant-cost key comparisons and swaps, reverse-ordered distinct sort keys cause $1+2+\cdots +(n-1)=n(n-1)/2$ comparisons and swaps. Thus worst-case time complexity is $O(n^2)$ in Big O notation. An already sorted array needs only $n-1$ key comparisons for $n\ge 1$ and no swaps. The adjacent-swap version uses constant auxiliary space complexity. Small or nearly sorted arrays can therefore make insertion sort useful despite its quadratic worst case.

Given a finite set of jobs with fixed half-open intervals $[s_i,f_i)$, where $s_i<f_i$, choose a subset $S$ of maximum cardinality. Each job occupies one shared resource throughout its interval. A feasible solution has pairwise disjoint intervals: for distinct selected jobs $i,j$, either $f_i\le s_j$ or $f_j\le s_i$. Thus a finish and the next start may coincide. Every job has value one; occupied time is not the objective function.^[ref]

Consider these six original jobs, with arbitrary time units:Job $B=[1,3)$ can be followed immediately by $C=[3,5)$ and $D=[5,7)$. Job $A=[0,6)$ conflicts with all three. Starting the resource earlier is therefore not automatically beneficial: one long commitment can displace several shorter requests.

The earliest-finish greedy algorithm uses a sorting algorithm to put jobs in nondecreasing finish time. Scan that order, accepting the first job and then each job whose start is at least the last accepted finish. Break finish-time ties arbitrarily; an empty input returns the empty set. For these jobs, the order and decisions areAfter $B,C$, job $A$ starts before the current finish five and is rejected. Accept $D$; then reject $E=[6,9)$ because six is before seven. Finally accept $F=[8,10)$. The result is $S=\{B,C,D,F\}$, with cardinality four. Leaving $[0,1)$ idle makes room for more jobs.

By contrast, the earliest-start rule scans $A,B,C,D,E,F$. It accepts $A$, skips $B,C,D$, accepts $E$, and skips $F$. Its feasible solution $\{A,E\}$ contains only two jobs. Here $A$ and $E$ meet at time six and are compatible; $E$ and $F$ overlap on $[8,9)$.

There is also an elementary optimality certificate for this example. The four subsets $\{A,B\}$, $\{C\}$, $\{D,E\}$ and $\{F\}$ form a partition of a set of the jobs. A feasible solution takes at most one job from each group: $A,B$ overlap, as do $D,E$, and each other group is a singleton. Hence four is an upper bound, attained by $\{B,C,D,F\}$. Checking all $2^6=64$ subsets gives a unique optimum of size four: $\{B,C,D,F\}$.

The earliest-finish theorem states that this greedy algorithm maximizes job count for every finite instance of interval scheduling. For the exchange argument, let $q$ be the first job in an optimal feasible solution and $g$ an earliest-finishing job. Every later selected job $j$ satisfiesReplace $q$ by $g$; compatibility and cardinality survive. The remainder must be optimal among jobs starting at or after $f_g$, or improving it would improve the whole selection. Mathematical induction on the smaller remaining instance, starting with the empty set, completes the outline.^[ref]

Why is the algorithm fast? Once sorted, each job is examined once, using only the last accepted finish to decide compatibility. The scan takes $O(n)$ time; comparison sorting algorithms give total time complexity $O(n\log n)$ for $n\ge 2$, in Big O notation, assuming constant-cost endpoint comparisons. Already sorted input needs only the $O(n)$ scan.^[ref]

The reason the shortcut is correct is stronger than "finishing sooner looks good": the exchange argument preserves every later job of a suitable optimum. This is the problem-specific fact that permits final decisions without exploring all subsets.

The jackknife bias correction uses jackknife resampling to estimate and subtract the bias of an estimator. Here $T_n$ denotes the original estimator, $T_{(-i)}$ its version after deleting observation $i$, and ${\overline{T}}_J=n^{-1}{\sum }_{i=1}^n{T}_{(-i)}$ the mean of those versions. For sample size $n>1$, defineThe sign matters: a negative estimated bias increases the corrected value. The original estimator and all deletion versions must target the same estimand and use the same estimation rule at their respective sample sizes. The definition alone does not make ${\tilde{T}}_J$ an unbiased estimator.

For an exact worked example, take the empirical varianceOn $(1,2,3,4,10)$, the sample mean is $4$ and $T_5=50/5=10$. Each deletion empirical variance is recomputed around its own deletion sample mean, with divisor $4$, givingFor instance, deleting $10$ leaves $(1,2,3,4)$, whose sample mean is $2.5$ and whose empirical variance is $1.25$. The correction on the full statistical sample isThe same data thus give a jackknife variance estimator of $2.5$ for the sample mean, and a corrected empirical variance of $12.5$; these are different estimands.

The exact equality with the usual sample variance is not an accident of these numbers. For any data with $n>1$, write $Q={\sum }_i(x_i-\overline{x}{)}^2=n{T}_n$. Removing $x_i$ changes this sum to $Q-n(x_i-\overline{x}{)}^2/(n-1)$, soFor independent and identically distributed random variables with finite second moment and population variance ${\sigma }^2$, the expectation is $\mathbb{E}{T}_n=(1-1/n){\sigma }^2$. Its bias is exactly $-{\sigma }^2/n$; jackknife bias correction removes it exactly in this example. Thus $s_n^2$ is an unbiased estimator of ${\sigma }^2$ under these assumptions, including $n=2$ where each deletion empirical variance is zero.

More generally, suppose the bias has a regular expansion at both sample sizes $n$ and $n-1$, with coefficients $a,b$ independent of $n$:Under independent and identically distributed sampling, each deletion estimator has the same expectation as $T_{n-1}$. Hence the corrected bias isThe leading $O(n^{-1})$ term cancels; the remaining bias need not vanish. The $O$ notation is big O notation. This argument presumes the expansion, rather than proving it for every statistic; the regularity conditions discussed for the jackknife variance estimator and statistical dependence still require care. Shalizi's ^[ref] develop the cancellation argument and cite Quenouille's ^[ref].

Kahn's algorithm maintains each remaining vertex's indegree, the number of its unfinished incoming directed edges, and a FIFO queue of ready vertices. Initialize the counts by scanning all directed edges and enqueue every vertex of indegree zero. Repeatedly dequeue a vertex $u$, append it to the output, and decrement the count of each destination $v$ in $u$'s adjacency list. Enqueue $v$ exactly when its count becomes zero. When the FIFO queue empties, accept the output if it contains all vertices; otherwise report a directed cycle. ^[ref]

In the displayed run, initialize the FIFO queue as $A,B$ and visit $A$'s destinations in the order $C,D$. Removing $A$ makes $C$ ready but leaves $D$ waiting for $B$. Removing $B$ then makes $D$ ready. Publication becomes ready only after both $C$ and $D$ are removed. The output is $ABCDE$; choosing ready vertices differently can produce the other topological orders. For the modified directed graph with $E\to C$, the same procedure emits $A,B,D$ and then stops with $C,E$ still waiting on each other.

The invariant is that each stored indegree counts incoming directed edges from unprocessed vertices. A ready vertex therefore has every prerequisite already in the output. If the FIFO queue empties with vertices left, every remaining vertex has a predecessor in the remaining directed graph; the predecessor argument gives a directed cycle. The unprocessed vertices can also include tasks blocked downstream of a directed cycle, so the leftover list alone is not a list of exactly the cyclic vertices.

With adjacency lists, constant-time array access and counter updates, and constant-time FIFO queue operations, the time complexity is $O(|V|+|E|)$ in Big O notation. Initialization scans all vertices and directed edges; each vertex is then enqueued at most once and each outgoing directed edge processed at most once. Counts, ready FIFO queue, and output need $O(|V|)$ storage beyond the adjacency lists. Shifting an array on every dequeue invalidates this bound. ^{[ref] [ref]}

The name refers to A. B. Kahn's 1962 paper "Topological sorting of large networks", published in Communications of the ACM, volume 5, issue 11, pages 558–562. Its abstract motivates topological sorting through network analysis and project planning. ^[ref]

// Target: foundations-of-mathematics.bigb

Count a fixed-base digit addition, subtraction, digit copy, or single-digit multiplication as constant cost. Base $B$ stays fixed as $n$ grows; an entire arbitrary-length integer multiplication is not one constant-cost step. With this model, splitting, sum formation, shifts and recombination require $O(n)$ digit operations. Ordinary digit-by-digit multiplication forms $n^2$ digit products for two $n$-position operands. The GMP base-case description uses this rectangular product arrangement.^[ref]

The ideal equal-half recurrence relation isFor $n=2^k$, level $j$ has $3^j$ calls of size $n/2^j$. If each internal call incurs exactly $\alpha$ times its size in additional digit work, that level contributes $\alpha n(3/2{)}^j$. There are $3^k=n^{{\log }_{2}3}$ leaves. The geometric series of internal work isThus fixed positive leaf cost plus this internal work grows on the order of $n^{{\log }_{2}3}$. In Big O notation, $T(n)=O(n^{{\log }_{2}3})$. Removing one of four products at every level matters much more than saving just one at the root.

The literal sum-based implementation instead admits the upper boundfor a nondecreasing worst-case cost envelope above a fixed base-case threshold. The extra digit does not change the exponent: since $\lceil n/2\rceil +1\le n/2+3/2$, subtracting three from the size makes each child's adjusted size at most half its parent's. Stop this comparison at any fixed threshold greater than three; its recursion depth is ${\log }_{2}n+O(1)$ and the level-work sum is bounded by the same geometric series up to constant factors. Exact call counts can depend on carries, zero shortcuts and the threshold, so they need not equal the ideal $3^j$ at each depth.

A disjoint-set data structure stores the current partition of a set of vertices into connected components of a graph. The operation $\mathrm{find}(v)$ returns a representative of the block containing $v$. Two vertices are in the same block exactly when their representatives agree. For each candidate edge $uv$, compare $\mathrm{find}(u)$ and $\mathrm{find}(v)$. Equal representatives mean reject; different representatives mean accept and perform $\mathrm{union}(u,v)$, merging the two blocks. The representatives are bookkeeping choices, not preferred vertices of the minimum spanning tree.

Every acceptance reduces the connected component of a graph count by one and increases the accepted edge count by one, preserving $|F|=|V|-c$. Thus the ledger reaches $c=1$ exactly when $|F|=4$. Only ten representative queries and four merges are needed for the five examined edges, counting two queries per examination and using the already found representatives for each merge. Neither breadth-first search nor reconstruction of a graph path is needed for these connectivity queries.

For $n=|V|$ and $m=|E|$, comparison sorting algorithm takes $O(m\log m)$ time for $m\ge 2$, using Big O notation. One simple disjoint-set data structure implementation stores each block as a rooted tree and attaches the smaller block's root below the larger block's root. Whenever a vertex's depth increases, its block size at least doubles, so its depth is at most $\lfloor {\log }_{2}n\rfloor$. Consequently each representative query or merge takes $O(\log n)$ time. Initialization plus the scan costs $O(n+m\log n)$; including sorting algorithm gives $O(n+m\log m+m\log n)$, hence $O(m\log m)$ for a connected input with $n\ge 2$. These are operation bounds, not measured timings.^[ref]

Suppose an analytic function near $c$ is not identically zero there. Its Taylor series has a first nonzero coefficient $a_m$, andThe term $a_m(z-c{)}^m$ is its leading Taylor term. Dividing by $(z-c{)}^m$ gives a limit of $a_m\ne 0$ as $z\to c$, so this term determines the leading local magnitude and angular behaviour. The remainder uses big O notation; it is smaller by one power near the centre.

For a real-valued analytic function of a real variable, an even integer $m$ gives the same nearby sign on both sides of $c$, while an odd integer $m$ gives opposite signs. For example, $f(x)=x^2(1+x)$ has leading Taylor term $x^2$ and is positive on both sides of zero sufficiently nearby; $g(x)=x^3(1+x)$ has leading Taylor term $x^3$ and changes sign there. The finite factor $1+x$ stays positive for $|x|<1$. The ordinary constant term is the leading one when $f(c)\ne 0$.

Let $C{a}_n=n^{-1}{\sum }_{j=1}^n{a}_j$ be the Cesàro mean of a sequence. If $|a_n|\le Cn$ for every positive integer $n$, the triangle inequality gives $|C{a}_n|\le C(n+1)/2\le Cn$. Mathematical induction repeats this estimate with the same constant for every iterate. An eventual $O(n)$ bound can be made global by increasing $C$ to absorb the finitely many initial terms. Consequently iterated Cesàro means preserve linear growth in Big O notation; this bound alone does not assert convergence or summability.

A maximal consecutive run of occupied or deleted slots in linear probing, bounded by never-used slots when any exist; adjacency wraps around by modular arithmetic. Deleted slots still belong to the search run.^[ref]

In the eight-slot example, array indices $0,1,2,3$ form one linear probing cluster. Inserting absent hash table key $10$ starts at $2$, passes the occupied slots $2,3$, and fills $4$. This extends the same linear probing cluster despite $10$ having a different initial array index from $0,8,16$. A hash collision at the initial slot is enough to make later slots compete too.

For a worst-case family, insert integer hash table keys $0,m,2m,\dots ,(n-1)m$ into an empty capacity-$m$ array, using the hash function $h_m(k)=k\mathrm{mod}m$, where $1\le n<m$. They occupy array indices $0,\dots ,n-1$. Lookup of absent $nm$ needs $n+1$ hash table probes. Taking $n=\lfloor m/2\rfloor$ gives hash table load factor at most $1/2$ while the number of hash table probes grows with $m$. Thus occupancy alone cannot promise constant lookup work.

Before any rebuilding, bounded lookup, deletion by hash table key, and insertion with a duplicate check each have worst-case $O(m)$ time complexity in Big O notation, assuming constant-cost hash function evaluation, array access and key equality. The counterexample gives a matching linear worst-case growth in the number of hash table probes. Hash table resizing is additional work; expensive string comparisons or hashing also fall outside these constant-cost assumptions.

Count just the equality tests between the target and an entry, excluding loop conditions and index updates. If the first match is at index $j$, linear search uses exactly $C=j+1$ equality tests. If the target is absent, it uses exactly $C=n$. Thus for $n\ge 1$ the best successful case costs one equality test, and the worst case costs $n$, attained by absence or a first match at the last index. For $n=0$, the sole outcome is absence with $C=0$.

An expected value needs a specified probability distribution. For $n\ge 1$, condition on success, assume the target occurs exactly once, and assume its position $J$ has a uniform distribution on a finite set of indices $0,\dots ,n-1$. Then the expected value of the linear search comparison count isThis is the average of the costs $1,2,\dots ,n$ under those assumptions, with no assumption that the array is sorted. It is not a universal average for arbitrary queries. For example, with $n=5$, a unique successful target at index $0$ with probability $3/4$ and at index $4$ with probability $1/4$ has expected value $(3/4)\cdot 1+(1/4)\cdot 5=2$, rather than $3$.

Duplicates also require care about what is sampled. Choose a position uniformly in $[7,4,7,2,9]$, then search for its value. All queries succeed, but the five possible sampled positions give costs $1,2,1,4,5$: both positions holding $7$ cause an immediate match at index $0$. The expected value is $13/5$, not $(5+1)/2$. Uniformly choosing an occurrence does not uniformly locate the first match.

More generally, let the success probability be $p>0$ and let $q_j$ be the conditional probability that the first matching index is $j$, allowing duplicates. Since ${\sum }_{j=0}^{n-1}{q}_j=1$, the expected value isUnder the unique, uniformly located successful-target assumptions this becomes $p(n+1)/2+(1-p)n$. If every query is absent, $p=0$ and $C=n$ without needing conditional probabilities. When $n=0$, success is impossible and $C=0$; the successful-search conditional formula is undefined.

Converting the linear search comparison count to execution time needs a cost model. Under constant-cost equality tests, next-entry access, and loop bookkeeping, worst-case time complexity is $O(n)$ in Big O notation for $n\ge 1$, with constant overhead even for the empty sequence. Variable-length entries can make an equality test expensive. On a linked list, advance along its links; repeatedly restarting at the head to obtain the next numeric index adds work that the comparison count does not capture. These are exact operation counts and conditional mathematical averages, not runtime measurements.

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]

Suppose the increment function of a one-step method is Lipschitz continuous in its solution argument with constant $K>0$, uniformly in time and step size. Let $e_n=y(x_n)-y_n$ be the global error, and let $h{T}_n$ be the exact-start local truncation error. The triangle inequality gives $|e_{n+1}|\le (1+hK)|e_n|+h|T_n|$. Iterating and summing a geometric series proves the displayed estimate. Since $(1+hK{)}^n\le e^{Knh}$, uniformly bounded $K$ and consistency error $O(h^p)$ give global error $O(h^p)$ on a fixed time interval when $e_0=O(h^p)$. Here $O$ denotes Big O notation. This is a constant-step form of the discrete Gronwall inequality.

When $g$ is nonzero sufficiently near the specified limit, little o notation meansThus the numerator becomes negligible relative to the denominator's scale. As $n\to \infty$, $n=o(n^2)$ because $n/n^2=1/n\to 0$; as $h\to 0$, $h^2=o(h)$ because $h^2/h=h\to 0$. The direction of the limit changes the comparison. ^[ref]

Equivalently, for every $\epsilon >0$, the bound $|f|\le \epsilon |g|$ holds sufficiently near that limit, with a threshold allowed to depend on $\epsilon$. Big O notation needs only one fixed multiplier, making it weaker. For example, $2n=O(n)$ but $2n$ is not $o(n)$. The useful relation $f\sim g⟺f-g=o(g)$ turns asymptotic equivalence into a statement about a negligible remainder.