Cost of find operation on a tree data-structure

Question

I implement my data sets with a tree data-structure.

The tree data-structure has a method named MakeSet which creates a set with one node. The tree data-structure has also a method named Merge(i,j) which merges trees of set i and set j in this way: the set with smaller depth becomes a child of the root of the set with larger depth.

I do MakeSet $n$ times and I do MergeSet $n-1$ times with a random order. Then I do a Find operation. What is the cost of Find in a worst case scenario?

---

I feel like the answer might be $O(n\log{n})$, because after doing $n$ MakeSet and $n-1$ MergeSet, it might be safe to say that we have a tree with $n$ nodes and height of $\log{n}$. I'm not sure.

Answer 1

Since my two comments already form the solution, I can also write the answer in total.

If you have a datastructure consisting of a bunch of trees, then the worst-case cost of a Find-Operation is the maximal height of a tree in your data structure. Your trees are built from $n$ trees consisting of a single node each by $n-1$ Merge-Operations. A Merge-Operation merges two trees such that the tree of smaller height is added to the root of the tree of larger height.

First observation: If you merge two trees of different height, then the resulting tree has the same height as the initial tree of larger height.

Second observation: If you merge two trees of the same height $h$, then the resultung tree has height $h+1$.

Conclusion: To increase the maximum height from $h$ to $h+1$, you first need two trees of height $h$.
So the worst-case scenario in your setting is the following: You initially merge two trees consisting of a single node each. This gives a tree of height $1$. You now need to merge two other trees consisting of a single node each such that a second tree of height $1$ occurs. If you now merge this trees of height $1$, then you have a resulting tree of height $2$. Now if you want to increase the height again, you need again $4$ of the initial trees to construct an other tree of height $2$.

The iteration of that argument shows that you can only increase the height $\log n$ times, where $n$ is the number of initial trees.