The constant that is practically constant

Every complexity result on this site so far has the same shape. The class is honest, and the constant it discards is where the information went: merge sort and heapsort are both $\Theta(n\log n)$ and one of them does 1.9 times the comparing. The class tells the truth and does not tell enough of it.

Union–find inverts it. Its bound is $O(m\,\alpha(n))$ for $m$ operations on $n$ elements, where $\alpha$ is the inverse Ackermann function, and the bound is tight — it is not merely an upper bound, there are inputs that achieve it. So the structure is provably not constant-time.

It is also, for every input that will ever exist, constant-time.

Both of those statements are true, they are not in tension, and the gap between them is the widest instance on this site of the notation describing something that is not what happens.

What the structure is #

Union–find maintains a partition of $n$ elements into disjoint sets. Two operations: find(x) returns which set $x$ is in, and union(a, b) merges two sets.

The implementation is a forest. Each element points at a parent; the root of a tree is the set’s name; find walks up to the root; union finds both roots and points one at the other. The cost of a find is the number of pointer hops it takes, which is the depth of the element, and everything about the analysis is about keeping trees shallow.

Two ideas do that, and they are independent:

Union by rank. When merging, point the shallower tree at the deeper one. A tree of rank $r$ has at least $2^r$ elements, so no rank exceeds $\log_2 n$ and no path exceeds it either. This bounds the depth before any find happens.

Path compression. When find walks from $x$ to the root, point every node on the way directly at the root. The walk was going to happen anyway, so the flattening is free, and every element on that path is depth 1 from then on. This shortens paths as a side effect of using them.

The famous result is about the pair: with both, $m$ operations cost $O(m\,\alpha(n))$. With either alone, the bound is $O(m \log n)$. With neither, the worst case is $O(mn)$.

Measuring the four cases #

Mean pointer hops per find, over $3n$ random unions from a stated seed:

Four things worth reading out of that, in increasing order of how surprising they are.

Neither optimisation is a catastrophe, and it grows like $n$. Quadrupling $n$ roughly quadruples the path length — 20.7, 79.0, 305.1, 1,222.2, 4,898.4, each about four times the last. Random unions build a tree of expected depth proportional to $n$ when there is nothing to stop them, and a find is walking most of it.

Either optimisation alone is enough to get almost all of the benefit. Both middle columns are under three at $n = 65{,}536$, against 4,898 for neither. Whatever the asymptotics say, the first optimisation applied is worth a factor of eighteen hundred and the second is worth a factor of three.

The two middle columns are not the same. Union by rank is flat — 1.43, 1.70, 1.68, 1.64, 1.70, drifting by 1.19 across the whole range. Path compression alone drifts upwards: 1.63, 1.79, 2.16, 2.43, 2.71, a factor of 1.66 and still climbing. Both are $O(\log n)$ in the worst case and only one of them looks logarithmic in the average. Rank bounds the depth in advance and the bound does not care how the finds arrive; compression only flattens paths that somebody walks, so an element never looked up stays where it is.

With both, the path length is under one. 0.92 hops per find, and it does not move: 0.896 at $n = 256$ and 0.921 at $n = 65{,}536$, a drift of 1.03 across two and a half orders of magnitude. Under one, because a find on a root costs zero hops and compressed forests are mostly roots and depth-one children.

α, tabulated rather than quoted #

The bound’s growth term is usually introduced as “the inverse Ackermann function, which is at most 4 for any practical $n$”, and then dropped. That phrasing is accurate and it hides the actual shape, which is stranger and easier to understand than the phrasing suggests.

$\alpha(n)$ is the least $k$ such that $A_k(1) \ge n$, where $A_k$ is the $k$-th function in the Ackermann hierarchy. The values of $A_k(1)$ are:

That is the whole function. It reaches 4 at $n = 2{,}048$ and the next step is at a number with no decimal representation — larger than the number of atoms in the universe by a margin that cannot be usefully described.

The site’s implementation computes α from that table rather than returning 4, and the gate requires both halves: that it never exceeds 4 for any $n$ up to $2^{53}$, and that it takes at least four distinct values across eight test sizes. A version implemented as () => 4 would satisfy the first and destroy the argument. A version that kept climbing would satisfy the second and be wrong.

Why this inverts everything else here #

Set the union–find result beside the sorting results and the asymmetry is the point.

Merge sort. Class $\Theta(n \log n)$, honest and tight. Constant 0.838 comparisons per $n\log_2 n$, and the constant is the difference between it and heapsort’s 1.613. The class tells the truth; the constant carries the information the class discards.

Union–find. Class $O(m\,\alpha(n))$, honest and tight — and $\alpha$ is 4 for every input, so the class overstates by describing a growth that never manifests. The measured constant, 0.92 hops per find, carries essentially all of the information, and the growth term carries none.

The two are not different in kind. Both are cases of a summary discarding what matters. What is unusual about union–find is which part is the summary: everywhere else the class is the reliable half and the constant is the missing half, and here the class is the misleading half.

There is a practical corollary that follows directly, and it is why this essay is in the graph field rather than the structures one. When choosing between union–find and something simpler, the $\alpha$ is not the consideration. The considerations are the 0.92 hops, whether the workload has enough finds for path compression to pay for its extra writes, and whether the sets need to be enumerated — which this structure cannot do without an extra pass. Anybody who declines union–find because “it is not quite constant time” has been misled by a correct theorem.

The two optimisations pay in different currencies #

The four-way table above counts pointer hops, which is the quantity α bounds and the one the theorem is about. Counting writes as well rearranges the comparison, and the rearrangement is the practical one.

Writes per find, over the same runs:

Union by rank is nearly free in writes — 0.218 per find, essentially just the one pointer each union redirects — because it changes nothing except which of two roots is chosen. Path compression writes 2.87 times per find, because flattening a path is a store per node on it.

So the two optimisations are not two ways of doing the same thing that happen to compose. Rank is a bound bought for nothing; compression is a bound bought with writes. Together they cost 1.14 writes per find and give 0.92 hops; rank alone costs 0.22 writes and gives 1.70 hops.

Whether the second is worth the first depends on what a write costs, which is the question the whole counting field keeps arriving at. Three cases where the answer is not “yes”:

A read-mostly structure shared between threads. Path compression makes find a mutating operation, so it cannot be called concurrently without synchronisation. Rank alone leaves find read-only. That is a much larger practical difference than 1.70 hops against 0.92, and no complexity table mentions it.

A structure in memory-mapped or persistent storage. Writes are pages dirtied. 2.87 writes per lookup on a structure backed by a file is a very different proposition from 0.22.

A short-lived structure with few finds per element. Compression’s cost is paid immediately and its benefit accrues to later lookups of the same elements. A run that touches each element two or three times may never collect it.

None of that argues against using both, which is the right default. It argues that “use union by rank with path compression, it’s α(n)” is a recommendation with three unstated preconditions, and that the measured columns say which precondition each of them is.

The bound is amortised, and that matters here #

$O(m\,\alpha(n))$ is a bound on $m$ operations together, not on each. It is an amortised bound, and union–find is the standard example of one that no simple summation proves — the potential-function argument for it is several pages and is the reason the result is famous.

The amortisation is real and visible in the measurement. Path compression makes an individual find expensive precisely when it is about to make many future finds cheap: the first find down a long path pays for the whole path, and every subsequent find on any element of it pays one. The mean is 0.92; the individual costs are not 0.92, and the distribution is the sawtooth-shaped thing that an amortised bound smooths away.

Which means the caveat that applies to every amortised bound applies here too. If the structure is used persistently — snapshot it, branch, use both branches — the accounting fails, because the credit that one find built up gets spent twice. Persistent union–find is a genuinely harder problem than persistent arrays and the known solutions are substantially slower. The bound in the table is a bound on linear use, and nothing says so.

The load is a dial as well as the size, and both are worth turning before a flat line is believed to be flat. More unions per element means longer chains for a structure with no compression and nothing at all for one that has it; more elements means the same. The four combinations are drawn again at each.

Where it appears in this field #

Kruskal’s algorithm is the reason union–find is in a graph collection at all. Sort every edge by weight; walk them in order; take an edge if its endpoints are in different components, which is one find each, and merge them, which is one union.

On a sparse graph of 2,048 vertices and 6,144 edges, Kruskal’s union–find work is 11,143 pointer hops in total, across 6,144 edges — under two per edge, against 42,385 comparisons spent in the sort. The component of Kruskal’s cost that the famous theorem is about is a quarter of the component nobody discusses.

That is the union–find result and the Dijkstra result arriving at the same conclusion from opposite directions. Dijkstra’s published bound describes a queue that turns out to be 2.7% of the work on a dense graph. Kruskal’s most celebrated component is 21% of the work on a sparse one. In both cases the analysis went where the mathematics was interesting, which is a perfectly good reason for analysis to go somewhere and not the same thing as where the time goes.

Where the fifth step is #

One number for scale, because “a tower of 2,049 twos” is not a quantity anybody can hold.

$\alpha$ steps from 4 to 5 at $A_4(1)$, which is $2$ raised to $2$ raised to $2$, two thousand and forty-nine times. Writing it in decimal would need more digits than there are atoms in the observable universe — not more atoms’ worth of paper, more digits than atoms.

So the statement “union–find is not constant time” is true, and the input that demonstrates it cannot be described, let alone constructed, let alone run. That is a strange kind of true, and it is why the measured 0.92 hops per find is the number that means something.

The compression that writes half as much #

The write column above prices path compression at 2.87 stores per find, and it is the only expensive thing in the structure. There are two variants that pay less for the same asymptotic bound, and they are worth knowing because the choice between them is decided by the numbers in that column rather than by anything in the theorem.

Full compression, as implemented here, walks to the root and then walks the path a second time pointing every node at it. Two traversals, one store per node.

Path halving does it in one traversal: while walking, point each node at its grandparent and then step to that grandparent. Every node visited is lifted one level and the walk advances two levels per iteration, so the path is roughly halved on each find with one store per two levels of descent — about half the writes, no second pass, and no extra state.

Path splitting is the same idea keeping every node: point each node at its grandparent and step to the node’s old parent, so every node on the path is lifted and the walk visits all of them. More writes than halving, fewer than full compression, and it flattens more per find.

All three achieve the $O(m\,\alpha(n))$ bound. The theorem does not distinguish them, which is exactly the situation this essay is about: a growth term that is 4 for every input cannot be the thing that decides between three variants whose difference is a factor of two in stores.

So the choice is made entirely on the constant, and the constant is the write count. For a structure in memory the difference is small and full compression’s shorter paths probably win. For one backed by a file, or shared between threads, or used a few times per element, halving’s single pass and halved stores is the better trade — and none of that is visible from the bound, because the bound is identical for all three.

The flat column is a fact about random unions #

One caution about reading the four-way table, and it applies to the column that looks best behaved.

Union by rank alone measures 1.43, 1.70, 1.68, 1.64, 1.70 — flat across a 256-fold range, and flatter than path compression alone. It would be easy to read that as evidence that rank alone is enough, or that its $O(\log n)$ bound is loose.

It is neither. Rank alone has a worst case of $\Theta(\log n)$ and the worst case is achieved: an adversary that merges equal-rank trees repeatedly builds a tree of depth exactly $\log_2 n$, and every find into its deepest leaf pays all of it. Nothing in the flat column contradicts that, because random unions do not merge equal-rank trees nearly often enough to build one.

What the column measures is that on random input the depth stays near the mean rather than the maximum, which is the distinction between an average and a bound in the place it is easiest to miss — a flat line invites the reading that the growth is absent rather than merely unexercised.

The honest summary of the four columns is therefore asymmetric. The unoptimised column’s growth is real and would appear on any input. The optimised columns’ flatness is a property of these inputs, and only the fully optimised one has a theorem saying it stays flat on all of them.

What the measurement is not #

Three limits, stated because the numbers above are unusually clean and clean numbers invite over-reading.

These are random unions. The worst case for union–find requires an adversary constructing a specific sequence, and the $\alpha$ term is about that adversary. Random unions do not approach it — nothing here is evidence about the worst case, only about the ordinary one, and that distinction has its own essay.

Pointer hops are not time. A hop is a dependent load: the address of the next node comes from the value of the current one, so a deep path is a chain of cache misses that cannot overlap. Union–find’s real cost on hardware is dominated by that, and 0.92 hops per find is good news precisely because the hops are the expensive part. The count is not the duration, as ever, and here the count is a better proxy than usual.

Path compression writes. Every hop on a compressed find is also a store, so the structure is not read-only and cannot be shared between threads without care. The measurement counts hops, and an implementation counting writes would rank the four combinations differently — union by rank alone performs no compression writes at all and its paths are shorter than compression alone manages. Which count is the right one depends on the workload, which is the choice the site keeps arriving at.