Lower Bounds for the Union–Find and the Split–Find Problem on Pointer Machines

摘要

A well-known result of Tarjan states that for allnandm⩾nthere exists a sequence ofn−1 Union andmFind operations that needs at leastΩ(m.α(m, n)) execution steps on a pointer machine that satisfies the separation condition. Later the bound was extended toΩ(n+m.α(m, n)) for allmandn. In this paper we prove that this bound holds on a general pointer machine without the separation condition and we prove that the same bound holds for the Split–Find problem as well.