A well-known result of Tarjan states that for all n and m = or > n there exists a sequence of n - 1 Union and m Find operations that needs at least Omega(m.alpha(m,n)) execution steps on a pointer machine that satisfies the separation condition. In other papers, the bound was extended to Omega(n+n.alpha(m,n)) for all m and n. In the paper they prove that this bound holds on a general pointer machine without the separation condition, and they prove that the same bound holds for the Split-Find problem as well.
展开▼
