Don't rush into a union
Mihai Pǎtraşcu, Mikkel Thorup · 2011
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 tu be the time to insert an edge and tq be the query time. For tu = Omega(tq), the problem is equivalent to the well-understood union-find problem: proc{InsertEdge}(s,t) can be implemented by Union(Find(s), Find(t)). This gives worst-case time tu = tq = O(lg n / lg lg n) and amortized tu = tq = O(α(n)). By contrast, we show that if tu = o(lg n / lg lg n), the query time explodes to tq ≥ n1-o(1). 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!