Analyzing time complexity of m operations in Union-Find structure

Question

The task is to find the time complexity in the worst case of m operations in Union-Find structure of "find" and "union", when all the "union" operations occur before all the "find" operations.

The union-find structure starts with n disjointed sets, that contain one element each. Moreover, each set is represented as a tree, and the structure uses path-compression and union-by-rank.

What i was thinking is that first of all, all the union operation together will take O(log(n)), because each one takes O(1), and there could occur not more than log(n) such operations.

After that if we look at the find elements then for each element the first find will take O(log(n)), but then the next time it will take O(1) for each element in its path. Therefore it will take less then O(m*log(n)).

I am not sure exactly how to continue from here. I thought that it will maybe take:

log(n) + log(n/2) + log(n/4) + .... = log(n)*log(n)

because every time the level of the path that we need to go up gets shorter.

However. I am not sure and also don't see where the m parameter is used here. Maybe there is also need to use the inverse Ackerman function in the analyze but I don't see how.

Answer 1

"find" operation (FindSet)

• Follow pointers from v "up the tree" to the root to find the set identifier of v
• When the recursive calls are returning the set identifier, each node changes its pointer from its parent to the root, compressing the tree
• No tree ranks (upper bound on height to the tree) are updated during "find" operation

"union" operation

• For each set or "tree", maintain a rank that is the upper bound on the height of the tree
• Root with the smaller rank (shorter tree) points to root with the larger rank (taller tree)
• Keeps trees "short"
• If two trees are of equal rank, one is chosen to point to the other. The rank of the tree is then incremented by 1

Time complexity

• We will perform O(E) "find" and "union" operations
• We perform V MakeSet operations
• "find", "union" and MakeSet take α(V) time (Inverse of Ackerman's function, very slow growing)
• This gives us O((V+E) α(V))
• |E| >= |V|-1, therefore Union-Find takes O(E α(V))
• α(V) is in O(log V) which is in O(log E)
• Therefore the time complexity of the Union-Find structure is O(E log E) or O(E log V)