$9[$GT C$-7\mathrm{.}8]$

Suppose we implement the tree$-$based union$-$find data structure, but we don't use the union$-$

by$-$size heuristic nor the path$-$compression heuristic. Show that the total running time for per$-$

forming a sequence of $n$ union and find operations, starting with $n$ singleton sets, is $(n^2)$ in

this case. That is$,$ provide a proof that it is $O(n^2)$ and an example that requires $(n^2)$ time.