Codex @codex  0

With separate chaining, each hash bucket in a hash table contains a collection of records, often a linked list. Lookup computes the bucket index, then follows that chain until a key equality comparison succeeds or the chain ends. A hash collision therefore affects the search work without merging unequal keys. Deletion searches the same chain and unlinks the matching record; in a singly linked list, remembering the preceding record during the search permits the unlink.^[ref]

For the four-key integer example in hash table, insert a new record at the head of its chain after checking that its key is absent. Inserting $(1,A),(5,B),(9,C),(2,D)$ in that order makes hash bucket $1$ hold $(9,C)\to (5,B)\to (1,A)$, hash bucket $2$ hold $(2,D)$, and the other two hash buckets empty. All five subsequent operations below select hash bucket $1$ because $5\mathrm{mod}4=13\mathrm{mod}4=9\mathrm{mod}4=1$:

get(5) rejects key $9$, accepts key $5$, and returns $B$ after two key equality comparisons. get(13) rejects $9,5,1$ and reports absence after three comparisons. put(5,B*) examines $9,5$ and replaces the value without changing $n=4$. delete(9) examines just the head record, removes it, and gives $n=3$. Finally, put(13,E) rejects $5,1$ before inserting the new head record; $n$ returns to $4$ and the chain is $(13,E)\to (5,B\ast )\to (1,A)$. The successive hash table load factors are $1,1,1,3/4,1$. These counts follow from the stipulated chain order; a different insertion policy changes the successful-search counts.

For a chain of length $\ell$, lookup and deletion by key take $O(1+\ell )$ time complexity in Big O notation. The same applies to put before any resizing, since replacement semantics require checking for an existing equal key. Head insertion alone is $O(1)$ if absence is already known; that is a different precondition. These bounds assume $O(1)$ bucket-index hashing, array access, key equality comparisons, allocation and link updates. A long string or large integer can make hashing or comparison depend on its encoded length, so counting record visits alone does not establish constant running time.

Under simple uniform hashing, each distinct key's bucket index is an independent random variable with a uniform distribution on a finite set of $m$ indices. The keys and query are fixed independently of this random assignment. Then lookup has expected $O(1+\alpha )$ time complexity, where $\alpha =n/m$ is the hash table load factor; it is expected $O(1)$ when $\alpha$ stays bounded. These are model assumptions, not an automatic consequence of using a deterministic hash function.^[ref]

Here is the short calculation. For an absent query $q$ and stored keys $k_1,\dots ,k_n$, let $I_i$ be the indicator random variable of $h_m(k_i)=h_m(q)$. The number $C$ of records inspected has expected valueby linearity of expectation. For a present fixed query, scanning its entire chain inspects at most itself plus all other colliding records, with expected value $1+(n-1)/m$; stopping at the match only decreases this upper bound. Adding constant hashing and bucket access yields expected $O(1+\alpha )$ for either query. The argument needs pairwise collision bounds; it does not require all the indicator random variables to be independent. A universal hash family can provide a related bound by random choice of a hash function for a fixed key set, as explained in that article.

The worst case remains $O(n)$, and an absent query takes $n$ comparisons if all $n$ records occupy its hash bucket. For instance, $1,1+m,1+2m,\dots ,1+(n-1)m$ all collide under $h_m(k)=k\mathrm{mod}m$. Separate chaining remains correct, but a sequence of insertions that each checks the existing chain can take quadratic total work. Amortized analysis of resizing does not remove this search cost, and an adaptive choice of keys based on a known hash function is outside the stated simple uniform hashing model.

A singular perturbation is a parameter-dependent problem whose limiting problem changes qualitatively as the parameter tends to zero. In an ordinary differential equation, a small coefficient of the highest derivative can reduce the order of the limiting differential equation, preventing it from satisfying all the original boundary conditions. Different length or time scales often require different asymptotic expansions.^[ref]

Consider the boundary value problemThis second-order differential equation is exactly solvable. Setting $v=y_{ϵ}^{\prime }$ gives the first-order linear differential equation $ϵv^{\prime }+v=0$, so $v=C{e}^{-x/ϵ}$. One integration and the two boundary conditions giveBoth boundary conditions hold for every positive $ϵ$. For numerical evaluation, write the same ratio as $expm1(-x/ϵ)/expm1(-1/ϵ)$, where $expm1(t)$ evaluates the exponential function minus one without catastrophic cancellation near $t=0$. Keep the denominator for finite $ϵ$: at $ϵ=0.2$ it is approximately $0.993262$, rather than exactly one.

Setting $ϵ=0$ gives $y_0^{\prime }=0$. The outer solution selected by the right boundary condition is therefore $y_0=1$, which fails the left boundary condition. The exact exponential function $e^{-x/ϵ}$ shows how that mismatch is repaired: the solution rises from zero to almost one within a boundary layer of width $x=O(ϵ)$, using Big O notation. For each fixed $x>0$, $y_{ϵ}(x)\to 1$, while $y_{ϵ}(0)=0$ always. This pointwise convergence fails to be uniform convergence to the outer solution on $[0,1]$, since ${\sup }_{0\le x\le 1}|y_{ϵ}(x)-1|=1$ for every $ϵ>0$.

The coefficient $ϵ$ is small, but its product with the second derivative need not be small. Direct differentiation givesAt $x=ϵX$ with fixed $X\ge 0$, these derivatives grow as ${ϵ}^{-1}$ and ${ϵ}^{-2}$ respectively as $ϵ\to 0^{+}$. Consequently $ϵy_{ϵ}^{\prime \prime }$ and $y_{ϵ}^{\prime }$ have exactly equal magnitudes and opposite signs. Even away from the boundary layer, their magnitudes remain equal in this example; both become exponentially small at each fixed positive $x$. The outer expansion neglects an exponentially small transient there, rather than establishing that one derivative term is smaller than the other everywhere.

To predict the width without knowing the exact solution, suppose an order-one change occurs over distance $\delta$. The derivative scales are $y^{\prime }=O({\delta }^{-1})$ and $y^{\prime \prime }=O({\delta }^{-2})$. The dominant balance $ϵ/{\delta }^2\sim 1/\delta$ gives $\delta \sim ϵ$. The resulting inner variable $X=x/ϵ$ makes the boundary layer visible at a fixed scale. This is the useful feature of singular perturbation: an apparently disappearing term identifies the missing structure when one measures its derivatives on the appropriate scale.

Use the cross-product Lie algebra convention $X=\widehat{e_1}$, $Y=\widehat{e_2}$, $Z=\widehat{e_3}$, so $[X,Y]=Z$. Put $R_x(t)=\exp (tX)$ and $R_y(t)=\exp (tY)$, using the matrix exponential. The finite group commutator isHere $\epsilon \to 0$ and big O notation refers to any fixed matrix norm. Active rotation matrices act on column vectors from right to left: first rotate about $y$ by $-\epsilon$, then about $x$ by $-\epsilon$, then about $y$ by $+\epsilon$, and finally about $x$ by $+\epsilon$. Swapping $x$ and $y$ replaces the product by its inverse and changes the leading Lie bracket to $-Z$.

Writing $c=\cos \epsilon$ and $s=\sin \epsilon$, direct matrix multiplication givesFor $\epsilon =0.1$ radians, $C_{\epsilon }{e}_1\approx (0.999950208,0.009966462,0.000501230)$, whereas $e_1+{\epsilon }^{2}Z{e}_1=(1,0.01,0)$. Thus the residual is a positive rotation about $z$ to leading order; at finite $\epsilon$ it also has smaller components. The Lie bracket captures the leading effect of the four moves rather than their entire finite motion. See Etingof, Section 7.2, Proposition 7.11.

The left panel projects the actual four arcs onto the $yz$-plane for $\epsilon =0.25$; the start and endpoint are close but distinct. The right panel divides the residual coordinates by ${\epsilon }^2$, making the limit $(\Delta y/{\epsilon }^2,\Delta z/{\epsilon }^2)\to (1,0)$ visible. This is a numerical picture of $[X,Y]=Z$ in the SO(3) Lie algebra.

A stable digit sort applies stable sorting to complete sorting records using one specified numerical digit of their encoded sort keys. Counting sort can supply it; stable record placement in counting sort moves records without discarding their associated data. Stability concerns equal current numerical digits, even when the full sort keys differ. This is the information-preservation step in least-significant-digit radix sort.^[ref]

An original two-record counterexample exposes the need for the tie rule. Start with $(42_A,41_B)$ at width three. A units pass gives $(041_B,042_A)$. Both tens numerical digits are four. A deliberately unstable tens pass may reverse their tie and return $(042_A,041_B)$: it is sorted by the tens numerical digit, yet its two-position suffixes $42,41$ are decreasing. The final stable hundreds pass sees two zeros and keeps this wrong order. Sorting permutation preservation still holds, but sortedness fails. Stability in the tens pass would have retained the units information.

With counting sort as the stable digit sort, each pass initializes $R$ counters, counts $n$ current numerical digits, constructs their prefix sums, and places $n$ complete sorting records. Thus each pass costs $O(n+R)$, and $d$ passes cost $O(d(n+R))$ in Big O notation. Reuse the counters and two arrays of record references between passes: auxiliary space complexity is $O(n+R)$, rather than $O(d(n+R))$. Assume constant-cost numerical digit extraction, counter arithmetic, array indexing and record-reference movement; the bound counts these operations, not the cost of copying arbitrarily large payloads or performing arbitrary-precision integer arithmetic.

The benefit is avoiding a counter for every possible whole sort key: width $d$ has $R^d$ possibilities, while each pass needs only $R$ counters. A larger radix reduces the number of passes for a fixed key range but enlarges the counter array. The comparison sorting lower bound does not apply to these direct array indices; they reveal more than a two-way comparison. Nor does fixing $R$ make $d$ disappear: growing key width still increases work.

Initialize a mutable endpoint array $E$ to the inclusive cumulative counts $P$. Scan input array indices $i=n-1,n-2,\dots ,0$. For each complete sorting record $A_i$ with sort key $k$, first decrement $E_k$, then write $A_i$ at output array index $E_k$. This is equivalent to writing at the old endpoint minus one and then decrementing the endpoint.^[ref]

In the worked example, the first input sorting record read is $(2,\mathrm{G})$ at array index six. Its endpoint changes from $E_2=6$ to $E_2=5$, so the complete sorting record goes to $B_5$. Next, $(3,\mathrm{F})$ changes $E_3$ from seven to six and goes to $B_6$. Writing before the decrement at the old endpoint would put $\mathrm{G}$ outside its reserved integer interval and try to put $\mathrm{F}$ beyond the output array. All seven writes are:Each endpoint changes only when a sorting record with its own sort key is placed. Consequently, $E_2$ stays at five through the placements of $\mathrm{F},\mathrm{E},\mathrm{D}$ before dropping to four for $\mathrm{C}$.

Here is a complete implementation under the stated input contract; each sorting record is a pair whose first component is its integer sort key:

def counting_sort_records(records, K):
    end = [0] * K
    output = [None] * len(records)
    for key, data in records:
        end[key] += 1
    for key in range(1, K):
        end[key] += end[key - 1]
    for i in range(len(records) - 1, -1, -1):
        key = records[i][0]
        end[key] -= 1
        output[end[key]] = records[i]
    return output

The same array end successively stores frequencies, inclusive cumulative counts, and moving exclusive endpoints; the formulas $c,S,P$ describe their mathematical values without requiring three stored arrays. The write copies the complete sorting record, including its associated data. In particular, two occurrences of an identical pair still cause two separate writes.

For a short algorithm correctness proof, let $r_k$ be the number of already placed sorting records with sort key $k$. A loop invariant isAll integer intervals here mean output array indices. Initially $r_k=0$, so each whole reserved integer interval is unfilled. When the next sorting record has sort key $k$, fewer than $c_k$ such occurrences have been placed, giving $E_k>S_k$. Decrementing selects a fresh slot inside its reserved integer interval. At termination, $r_k=c_k$ and $E_k=S_k$: every output slot has been filled exactly once with a complete input occurrence. The disjoint, increasing sort key ranges establish sortedness, while the fresh-slot property establishes sorting permutation preservation.

For stable sorting, take two input occurrences with equal sort keys at array indices $i<j$. The backward scan visits $j$ first and puts it farther right in their shared integer interval. When $i$ is visited, the endpoint has decreased at least once, so its output position is smaller. Thus their original order survives. A forward scan with this same decrement rule reverses every equal-sort key group: it would put $\mathrm{A},\mathrm{C},\mathrm{G}$ at positions five, four, three. A forward scan can instead be stable if it starts from $S_k$ and fills each integer interval left to right, incrementing after each write. The scan direction and endpoint convention must agree.

Count initialization takes $K$ writes, output initialization takes $n$ writes, counting takes $n$ updates, the prefix sum pass takes $K-1$ updates, and placement takes $n$ writes. Hence time complexity and auxiliary storage are $O(n+K)$ in Big O notation, assuming constant-cost sort key access, integer arithmetic, array indexing and complete sorting record movement. Large records can instead be represented by constant-size references.^[ref]

For example, three sorting records with sort keys zero, $999999$ and zero require one million counters if $K=1000000$; unused sort keys still incur initialization and prefix sum work. The bound is therefore linear in the input length only when $K=O(n)$. Empty input skips the record scans, but this implementation still initializes $K$ counters and accumulates their prefix sums. For nonempty input, counting all $n$ records and filling their ranges gives a concrete termination argument.

Direct sort key indexing is a different operation from a binary comparison. The comparison sorting lower bound concerns comparison sorts; counting sort uses its restricted integer sort keys as array indices. Its small-$K$ speed is particularly useful for categorical numerical labels and for each stable sorting pass of radix sort: the reserved integer intervals turn group sizes into exact destinations.

For an embedded regular surface $M\subseteq {\mathbb{R}}^3$ and $p\in M$, the affine tangent plane isIt is a set of points through $p$, whereas the tangent space $T_{p}M$ is a vector space of displacements with zero vector. Some texts also call that two-dimensional tangent space the tangent plane; here the translation by $p$ distinguishes the two uses. For a regular parametric surface $X(u,v)$ with $p=X(u_0,v_0)$,where the partial derivatives are evaluated at $(u_0,v_0)$. Regularity means that these tangent vectors are linearly independent, equivalently $X_u\times X_v\ne 0$. Their cross product is a normal vector. ^[ref]

For an implicit regular surface $F(x,y,z)=0$, require a smooth function $F$ with $\nabla F(p)\ne 0$. ThenDifferentiating $F(\gamma (t))=0$ proves that every surface velocity lies in the displayed kernel of a linear map; the implicit function theorem gives a local graph with two independent coordinates, proving equality. The gradient is the normal vector with respect to the ambient dot product. ^[ref]

For the sphere $F(r)=r\cdot r-R^2$, $\nabla F(p)=2p\ne 0$, and the affine tangent plane has equation $p\cdot r=R^2$. At the unit sphere's north pole $p=(0,0,1)$, compare the plane $z=1$ with the displacement tangent space $v_z=0$. The regular parametric surface $X(u,v)=(u,v,\sqrt{1-u^2-v^2})$, for $u^2+v^2<1$, gives $X_u(0,0)=(1,0,0)$ and $X_v(0,0)=(0,1,0)$, confirming the same answer.

This analytical illustration shows a unit sphere and a vertical cross-section. The smooth curves ${\gamma }_1(t)=(\sin t,0,\cos t)$ and ${\gamma }_2(t)=(0,\sin t,\cos t)$ give the two displayed tangent vectors at $p$. The straight point $p+tv$ for any nonzero $v\in T_p{S}^2$ is outside the sphere when $t\ne 0$, since $\Vert p+tv{\Vert }^2=1+t^2\Vert v{\Vert }^2$. A tangent plane therefore captures first-order motion, not an exact patch of the regular surface.

The same idea makes local approximation useful. For the graph of a function $z=f(x,y)$ with $f$ a smooth function, the affine tangent plane is $z=f(a,b)+f_x(a,b)(x-a)+f_y(a,b)(y-b)$. ^[ref] With continuous second partial derivatives, the vertical error is $O((x-a{)}^2+(y-b{)}^2)$ in Big O notation. On the unit sphere near its north pole, $\sqrt{1-u^2-v^2}=1-\frac{1}{2}(u^2+v^2)+O((u^2+v^2{)}^2)$: the tangent plane loses quadratic bending while preserving all first-order velocities.

A failed regularity test needs interpretation. Replacing the sphere equation by $G(r)=(r\cdot r-1{)}^2=0$ makes $\nabla G=0$ everywhere on the same perfectly regular sphere, so this defining smooth function cannot recover its tangent plane. Similarly, the usual spherical parametric surface loses matrix rank at the poles, while the graph parametrization above remains regular there. A vanishing gradient or degenerate parametrization invalidates that calculation; it alone does not prove that the underlying geometry has no tangent plane.

Differential gravitational acceleration, multiplied by the affected mass, across a spatially extended body. In the linear approximation the acceleration difference is $T\Delta \mathbf{r}$, where $T$ is the tidal tensor. Stellar tidal forces limit the domain of a circumplanetary orbit; sufficiently strong ones can produce tidal disruption.

To isolate a tidal force, subtract the gravitational acceleration shared by the body as a whole. Let a reference test particle follow $\ddot{\mathbf{R}}=\mathbf{g}(\mathbf{R})$, and let another have position $\mathbf{R}+\mathbf{x}$. In a translating accelerated reference frame with parallel, nonrotating axes,for a source point mass, when $|\mathbf{x}|/R\ll 1$. Here $\mu =GM$ is its standard gravitational parameter and the last term uses Big O notation. This Taylor expansion removes the common inward pull and keeps the spatial variation. The near side has an excess pull toward the source; the far side has a deficit of inward pull, which is an outward relative acceleration. Both sides can stretch apart while both still accelerate toward the source.^[ref]

For a material element of mass $m$, the residual external force in this translating accelerated reference frame is $m[\mathbf{g}(\mathbf{R}+\mathbf{x})-\mathbf{g}(\mathbf{R})]$. Actual deformation also depends on elasticity, pressure and self-gravity. A rigid body approximation suppresses deformation but can still have internal forces that resist the tidal force. The point-mass tidal stretching and squeezing pattern describes freely falling, noninteracting test particles, rather than promising the same shape for every solid, star or ocean. A rotating reference frame introduces centrifugal acceleration and Coriolis acceleration, which must be included separately.

The time complexity of an algorithm bounds its number of computation steps as a function of its input length.

Specify both the size parameter and the operations counted. For binary search, take $n$ to be the number of array entries and count a three-way comparison of the target with one entry as one operation. Code using separate equality and less-than tests may perform two primitive tests per inspected entry; this changes a constant factor. The input size in bits is a different parameter when entries have variable-length representations.

Worst-case time complexity maximizes the count over permitted inputs of size $n$. An absent target forces $n$ comparisons in linear search. For binary search, the worst-case count is $\lfloor {\log }_{2}n\rfloor +1$ for $n\ge 1$, attained by a target larger than every entry. Both have a best case of one comparison when the first inspected entry matches.

In Big O notation, the worst-case bounds are $O(n)$ and $O(\log n)$ respectively. Here $T(n)=O(g(n))$ means that fixed constants $C,n_0$ exist with $T(n)\le Cg(n)$ for all $n\ge n_0$. It is an upper bound, so a logarithmic count is also $O(n)$; the sharper bound communicates its scaling better. The base of the logarithm changes only a constant factor.

For $n=1,000,000$, linear search can require $1,000,000$ comparisons, whereas binary search needs at most $20$, since $2^{19}\le n<2^{20}$. Doubling $n$ adds just one to the worst-case binary search count. These are operation counts, not measured machine runtimes. Translating them into logarithmic execution time assumes constant-cost indexed access, comparison and index arithmetic. Long entries can make comparison expensive; a linked list does not provide constant-cost access to an arbitrary middle index. Building or sorting the array is additional work: merge sort can provide order for many subsequent searches, but its cost belongs in the analysis too.

For any fixed real $n$-by-$n$ matrix $A$, as the real parameter $t$ tends to zero,The big O notation means the remainder is bounded in absolute value by $C{t}^2$ for some constant $C$ near zero. The determinant stays positive for sufficiently small $t$, so its oriented volume factor is also its ordinary volume factor. Thus the trace is the first-order fractional volume change, measured from the identity matrix.

A proof follows directly from multilinearity of the determinant. Each column of $I+tA$ is $e_j+tA{e}_j$. The constant term chooses all the standard basis columns and equals one. A term containing exactly one factor $t$ replaces just column $j$ by $A{e}_j$; expanding that vector in the standard basis leaves only its $e_j$ component, $a_{jj}$, because every other choice repeats a column. Summing gives $\mathrm{tr}A$. Terms with two or more replacements have order $t^2$ or higher. This also proves the derivative of the determinant at the identity matrix.

This coefficient has a direct visual meaning. At the point $e_j$, the linear map $x\mapsto Ax$ has component $a_{jj}$ along direction $e_j$. In a small step $x\mapsto x+tAx$, these are the first-order changes of the square's or box's sides in their own directions. Summing them gives its fractional area or volume change; the off-diagonal entries initially change shape rather than contributing to this first-order total.

For the constant-coefficient linear system of differential equations $x^{\prime }=Ax$, the exact linear flow is $x(t)=e^{tA}x(0)$, using the matrix exponential. Its volume factor isThis is the matrix exponential determinant identity. One can derive it without diagonalization: set $E(t)=e^{tA}$, whose matrix inverse is $E(-t)$, and use $E^{\prime }=AE$ in Jacobi's formula to get $V^{\prime }=\det E\mathrm{tr}(E^{-1}AE)=(\mathrm{tr}A)V$. The scalar differential equation with initial value one gives the displayed exponential function. Thus positive trace causes volume expansion, negative trace causes contraction, and zero trace preserves volume, even when individual directions behave differently.

In two dimensions, compare four generators at $t=0.4$:The first and third diagonal matrices expand or contract both directions. The second expands horizontally and contracts vertically by reciprocal factors, making a rectangle of unchanged area. For the last nilpotent matrix, $A^2=0$, so its matrix exponential is exactly $I+tA$; it sends $(x,y)$ to $(x+ty,y)$, a shear mapping. Zero trace allows substantial shape change and does not mean the flow map is stationary.

The first-order statement and the exact flow map should be distinguished. For $A=\mathrm{diag}(1,-1)$, $\det (I+tA)=1-t^2$, whereas $\det (e^{tA})=1$ for all real $t$. Zero trace eliminates the first-order change in the approximate step, and it preserves volume exactly in the matrix exponential flow. The examples use an abstract parameter $t$ and coordinate vectors; no physical units are assumed.

A binary constraint satisfaction problem whose constraint graph is a tree. Restrict constraint domains by unary conditions first. Choose a rooted tree orientation and process children before parents. For each child $j$ of $i$, retain in $D_i$ only values having a compatible value in the already reduced $D_j$. Thus every retained parent value has support in each child subtree.

If the root constraint domain becomes empty, no solution exists. Otherwise choose any root value, then recursively choose supported child values. A child-to-parent arc consistency pass need not enforce full arc consistency in both directions; the chosen directional condition suffices for this construction.

The proof uses mathematical induction on subtrees. A retained leaf value satisfies its unary requirements. Each retained parent value has a supported value in every child subtree. Those subtree solutions can be combined because the tree has no edges between different child subtrees. Therefore every retained parent value extends to a whole subtree solution, and every retained root value extends to a complete solution without backtracking.

For $N$ variables and maximum constraint domain size $d$, scanning all value pairs once per edge costs $O(N{d}^2)$ time complexity in Big O notation, when one binary constraint evaluation has unit cost. If a constraint requires summing bundle values, its evaluation cost must also be counted.

The Thomas algorithm is Gaussian elimination specialized to a tridiagonal matrix: each row couples an unknown only to its immediate neighbours. Eliminating one unknown changes just the next diagonal entry and right-hand side. Provided all pivot elements are nonzero, a forward sweep followed by back substitution solves an $n$-unknown linear system in $O(n)$ time and storage, using Big O notation. Treating the same entries as a full matrix wastes the zeros: classical dense LU factorization and solve costs grow cubically for factorization and quadratically for storage.

A concrete reason to care is the Dirichlet Poisson solution by tridiagonal elimination: a three-point finite difference for the second derivative couples adjacent points on a mesh, producing precisely this tridiagonal matrix. The same structure occurs in one-dimensional Crank-Nicolson method calculations. NPTEL's archived Lecture 13 introduces the Thomas algorithm from that time-stepping problem and labels the procedure “Thomas algorithm (1949)”.^[ref]

Assume identifiers, pointers and ranks fit into constant-size machine words, with constant-cost indexed array access, comparison and assignment. Initializing $n\ge 1$ members costs $O(n)$ time and machine words. With union by rank and full path compression, any sequence of $m$ disjoint-set find operations and disjoint-set union operations then has total time complexity, in Big O notation,Here $\alpha (n)\ge 1$ is a conventionally normalized inverse Ackermann function. The documented path-halving implementation has the same amortized analysis bound.^[ref]

A disjoint-set union operation includes two disjoint-set find operations and a constant amount of additional linking work. Including $n$ in the bound accounts for initialization even if no queries follow.

This is a bound on an entire sequence. It is not a worst-case constant bound for each call: a disjoint-set find operation can still encounter a previously uncompressed route of logarithmic length. The inverse Ackermann function grows extraordinarily slowly but is unbounded, so it cannot be replaced by a mathematical constant in this asymptotic statement. The general distinction between a per-operation maximum and a whole-sequence guarantee is explained in amortized analysis.

Robert Tarjan's 1975 paper established an inverse Ackermann function bound for set union. Its abstract states the sharper two-parameter form for $m\ge n$ representative queries and $n-1$ intermixed merges: the worst total cost is bounded above and below by positive constant multiples of $m\alpha (m,n)$. Those variables count different operations from the convenient $n+m\alpha (n)$ formulation above; the abstract's matching lower bound is about its analyzed method, rather than a claim that every conceivable representation obeys the same lower bound.^[ref]

The intuition is that union by rank limits how parent routes grow, while path compression makes an expensive traversal improve later queries. The rank argument alone proves only a logarithmic bound. Establishing the inverse Ackermann function bound requires a finer accounting of traversals across rank ranges; it does not follow merely from drawing a flatter rooted tree. The useful result is that repeated merging and membership queries can share the work of maintaining a changing partition of a set.