Don't Rush into a Union: Take Time to Find Your Roots

Original · EN

We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting tᵤ be the time to insert an edge and tq be the query time. For tᵤ = Omega(tq), the problem is equivalent to the well-understood union-find problem: InsertEdge(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time tᵤ = tq = O(lg n / lglg n) and amortized tᵤ = tq = O(alpha(n)). By contrast, we show that if tᵤ = o(lg n / lglg n), the query time explodes to tq >= n¹⁻ᵒ⁽¹⁾. In other words, if the data structure doesn't have time to find the roots of each disjoint set (tree) during edge insertion, there is no effective way to organize the information! For amortized complexity, we demonstrate a new inverse-Ackermann type trade-off in the regime tᵤ = o(tq). A similar lower bound is given for fully dynamic connectivity, where an update time of o(n) forces the query time to be n¹⁻ᵒ⁽¹⁾. This lower bound allows for amortization and Las Vegas randomization, and comes close to the known O(lg n * poly(lglg n)) upper bound.