Lower bounds for the union-find and the split-find problem on pointer machines
Johannes A. La Poutré · 1990
A well-known result of Tarjan (cf.[15]) states that for all n and m >_ n there exists a sequence of n -1 Union and ra Find operations that needs at least f~(m.c~(m, n)) execution steps on a pointer machine that satisfies the separation condition.In [1,16] the bound was extended to f~(n + m.t~ (m, n)) for all m and n.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.