What is the worst case efficiency for a path compression algorithm?

In a Union-Find (Disjoint Set) structure, N elements are stored as a forest of trees, and Union merges two trees while Find follows parent links up to a tree's root to identify which set an element belongs to. Path compression is the optimisation applied inside Find: once the root is located, every node visited on the way up is re-linked directly to that root, flattening the tree so later Find calls on those nodes become cheaper.

Consider a structure of N elements subjected to a sequence of up to N-1 Union operations and M ≥ N Find operations (the usual convention, since a sequence that is short relative to N is not the interesting case), with path compression applied on every Find but WITHOUT additionally balancing unions by rank or size — so, before any compression happens, a single tree can degenerate to height O(N) in the worst case. Tarjan's classical worst-case analysis of set-union algorithms shows that even so, path compression's amortising effect (once a long path is flattened by one expensive Find, every later Find revisiting those same nodes becomes cheap) bounds the total time to process the whole sequence at O(N + M log N), which simplifies to O(M log N) once M ≥ N — a bound on the aggregate cost of the whole sequence, not a claim that any single tree stays at height O(log N).

This O(M log N) figure is the sequence-wide bound (for M ≥ N) when path compression is used ALONE. Two related but distinct techniques are often confused with it: union BY RANK alone (without path compression) keeps every tree's height at O(log N), so a single Find under that scheme costs O(log N) — a per-operation guarantee that path compression alone does not provide. Combining path compression WITH union by rank/size gives the strongest result: the amortised cost drops to nearly O(α(N)) PER operation, where α is the extremely slow-growing inverse-Ackermann function, so the whole sequence costs about O(M α(N)) — the near-constant-per-operation result usually quoted for a fully optimised Union-Find. Path compression used alone, however, keeps the whole sequence at O(M log N).

• O(N log N) matches the familiar running-time shape of a comparison-based sort over N elements, not the cost of a sequence of Find calls on a Union-Find structure — the two are easy to conflate since both commonly show a logarithmic factor, but they measure fundamentally different processes: sorting a fixed collection once, versus repeatedly querying a structure that changes as unions happen.

• O(log N) is the guaranteed per-Find cost when trees are kept balanced by union BY RANK ALONE (no path compression) — a different technique's per-operation guarantee, not the sequence-wide bound that applies when path compression alone (without rank balancing) is the only optimisation in use.

• O(N) is the worst-case cost of a single Find on a tree that is neither rank-balanced nor yet compressed — the raw, fully degenerate case before path compression has had any chance to flatten it, not the bound on the total cost across the whole sequence of M Find calls.