On the single-operation worst-case time complexity of the disjoint set union problem

We give an algorithm for the disjoint set union problem, within the class of algorithms defined by Tarjan, which has $O(\log n / \log \log n)$single-operation time complexity in the worst case. Also we define a class of algorithms for the disjoint set union problem, which includes the class of algorithms defined by Tarjan. We prove that any algorithm from this class has at least $\Omega(\log n / \log \log n)$ single-operation time complexity in the worst case.