The complexity of add/find(collision), would depend on the implementation of union.

If you are using some hashtable based datastructure then your collision operation will indeed be constant assuming a good hash function.

Otherwise, add will probably be O(Log(N)) for a sorted list/tree datastructure.

Let's assume for the moment, that each tree of height h contains at least 2^h nodes. What happens, if you join two such trees?

If they are of different height, the height of the combined tree is the same as the height of the higher one, thus the new tree still has more than 2^h nodes (same height but more nodes).

Now if they are the same height, the resulting tree will increase its height by one, and will contain at least 2^h + 2^h = 2^(h+1) nodes. So the condition will still hold.

The most basic trees (1 node, height 0) also fulfill the condition. It follows, that all trees that can be constructed by joining two trees together fulfill it as well.

Now the height is just the maximal number of steps to follow during a find. If a tree has n nodes and height h (n >= 2^h) this gives immediately log2(n) >= h >= steps.

Firstly, here is the precise statement of the case 2 in OP's question.

A sequence of m MAKE-SET, UNION, and FIND operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank in worst-case time .

In fact, it is trivial to see that the MAKE-SET and UNION operations run in time. So the question is really about the time-complexity of the FIND operation.

Here are the properties of the disjoint-set forest you can prove.

1. Given any node that has been added to the set of union-find data structure, the ranks of the nodes in a path from to its root is strictly increasing.
2. A node which is root of a sub-tree with rank has at least nodes. (This fact can be proved by induction on ).
3. Every node has rank at most .

With properties 1 and 3, it should be easy to prove the desired time complexity.

The above explanation follows roughly the section 21.4 in Introduction To Algorithms, third edition by CLRS. Readers are encouraged to read the chapter 21 of that book.

The answer to your question depends heavily on the representation of the sets. For simplicity, I am assuming that we have $n$ sets of integers, where all the integers are between $0$ and $n-1$ (conforming to your statement that the $n$ sets each have up to $n$ elements).

• If the sets are represented in a generic set data structure such as a hash table, as pointed out in the comments, that means even reading the input takes $\Omega(n^2)$ time in the worst case. This implies that it is completely impossible to avoid the $n^2$ algorithm of unioning all the sets together.

• One common compact representation of sets for practical results is using bit-vectors. If the length of a machine integer is 8 bytes (64 bits), then we represent a set of up to $n$ elements using a bit-vector of length $n$ which is represented as an array of $\frac{n}{64}$ integers. As bitwise xor is an $O(1)$ hardware operation, unioning two of these sets only takes $\frac{n}{64}$ time, and doing this $n$ times we have $O(\frac{n^2}{64})$ for the whole union. Still quadratic, but much better in practice.

• There are other interesting representations of sets. One representation is using logical predicates: a set here is a formula $\varphi(n)$ which is true exactly when $n$ is in the set. For example, the set of all integers between $1$ and $10000$ would be represented as the predicate "$1 < n < 10000$" (expressed as a syntax tree). Unioning this kind of predicate together can be much faster than unioning the sets, if the sets are of a simple structure, like ranges ("$1 < n < 10000$"), unions of a few different cases ("$n < 5 \text{ or } n = 10$"), or specific elements ("$n = 5$"). When unioning, we apply simplifications to the resulting predicates (e.g., "$x \text{ or } x$" simplifies to "$x$").

• Finally, extending this, one way of representing predicates that happens to be especially effective is using a binary decision diagram, which is kind of like a decision tree. These structures lead to a pretty compact encoding of common sets like ranges and predicates. They can be unioned together efficiently in $O(m)$ where $m$ is the size of the BDD structure, so the total time will be $O(m \cdot n)$. For both this and the formula representation, there is a necessary assumption that the sets we are unioning together are "not too complex" and have a more compact representation than just listing out the elements. But, even in the worst case, it only takes $O(n \log n)$ space to store a set of $n$ elements explicitly as a BDD, so we aren't paying much of a cost, and in practice, the sets will often overlap significantly and we will get a more compact representation.

In your code, you are using std::set's. In the C++ standard library, unfortunately, std::set's are ordered (and we have std::unordered_set). Thus, most of the "hard work" in your code is actually converting the vectors into ordered sets; that takes O(n log(n) + m log(m)) time. The union is - almost certainly - linear, as @StPiere suggests, so an additional O(n+m) time.

Without path compression : When we use linked list representation of disjoint sets and the weighted-union heuristic, a sequence of m MAKE-SET, UNION by rank , FIND-SET operations takes place where n of which are MAKE-SET operations. So , it takes O(m+ nlogn).

With only path compression : The running time is theta( n + f * ( 1 + (log (base( 2 + f/n)) n ) ) ) where f is no of find sets operations and n is no of make set operations

With both union by rank and path compression: O( m*p(n )) where p(n) is less than equal to 4

Seidel and Sharir proved in 2005 [1] that using path compression with arbitrary linking roughly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$.

See [1], Section 3 (Arbitrary Linking): Let $f(m,n)$ denote the runtime of union-find with $m$ operations and $n$ elements. They proved the following:

Claim 3.1. For any integer $k>1$ we have $f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$.

According to [1], setting $k = \lceil m/n \rceil + 1$ gives $$f(m, n)\leq (2m+n) \log_{\lceil m/n\rceil +1}n$$.

A similar bound was given using a more complex method by Tarjan and van Leeuwen in [2], Section 3:

Lemma 7 of [2]. Suppose $m \geq n$. In any sequence of set operations implemented using any form of compaction and naive linking, the total number of nodes on find paths is at most $(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$ With halving and naive linking, the total number of nodes on find paths is at most $ (8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil $.

Lemma 9 of [2]. Suppose $m < n$. In any sequence of set operations implemented using compression and naive linking, the total number of nodes on find paths is at most $ n + 2m \lceil \log n\rceil + m$.

[1]: R. Seidel and M. Sharir. Top-Down Analysis of Path Compression. Siam J. Computing, 2005, Vol. 34, No. 3, pp. 515-525.

[2]: R. Tarjan and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, Vol. 31, No. 2, April 1984, pp. 245-281.