Suppose we are using union$-$by$-$size but not path compression in our disjoint set

implementation and have $2^$nitems $1,2,...,2^$n$,$ initially each in its own set.

$($a$)$ Find a set of $2^$n $1$ unions that lead to the worst$-$case $($i$.$e$.,$ largest$)$ average depth in the final tree for n $=2.$ Do the same for n $=3.$ Be sure to specify the average depth for

each of your trees.

$($b$)$ Let D$($n$)=$ the worst case average depth when combing $2^$n items using $2^$n $1$ unions.

Find a closed expression for D$($n$)$ and prove it is correct. HINT: Two approaches to this problem are the following: $1)$ derive a recurrence relation for D$($n$)$ and solve it$,$ or $2)$ guess an answer for D$($n$)$ using the two examples in part $($a$)$ and prove it$$s correct using induction.