Complexity: Inverse Ackermann in Plain Words

The code below compares the deepest node in a tree built without optimizations against one built with both optimizations.

def depth(parent, x):
    d = 0
    while parent[x] != x:
        x = parent[x]
        d += 1
    return d

n = 1 << 12
naive = list(range(n))
for i in range(1, n):
    naive[i - 1] = i            # hang the previous root under the next element
print(max(depth(naive, x) for x in range(n)))   # 4095

parent, size = list(range(n)), [1] * n
def find(x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
for i in range(1, n):
    ra, rb = find(i - 1), find(i)
    if size[ra] < size[rb]:
        ra, rb = rb, ra
    parent[rb] = ra
    size[ra] += size[rb]
print(max(depth(parent, x) for x in range(n)))  # 1

With union by size, each new singleton is hung directly under the root of the big tree, so the maximum depth stays at 1.

Timing operations

Run 200,000 random unions while growing the number of elements a thousandfold. The time per operation stays in the low microseconds and does not grow in proportion to n. Depending on your machine it may creep up a little, mostly because larger arrays fit less well in the CPU cache, not because the algorithm does more work.

import random
import time

def ns_per_op(n, m=200_000):
    parent, size = list(range(n)), [1] * n
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    start = time.perf_counter()
    for _ in range(m):
        ra, rb = find(random.randrange(n)), find(random.randrange(n))
        if ra != rb:
            if size[ra] < size[rb]:
                ra, rb = rb, ra
            parent[rb] = ra
            size[ra] += size[rb]
    return (time.perf_counter() - start) / m * 1e9

for n in (10**3, 10**5, 10**6):
    print(n, f"{ns_per_op(n):.0f} ns/op")

Space complexity

Two arrays, parent and size (or rank), give O(n) space. Ranks never exceed log n, so a very small integer type is enough for them. A recursive find can push as many stack frames as the tree is tall in the worst case, so in languages with a low recursion limit, such as Python, the iterative version is the safe choice.

import sys
# If you must use a recursive find, you may need a higher limit
sys.setrecursionlimit(1 << 20)

def find_rec(parent, x):
    if parent[x] != x:
        parent[x] = find_rec(parent, parent[x])
    return parent[x]

Comparison with alternatives

Summary

With both optimizations, union-find runs m operations in O(m α(n)) time and O(n) space. Since α(n) is at most 4 for any realistic input, you can treat it as a constant. When edges are never deleted and queries are frequent, it is far more efficient than rerunning BFS or DFS.