4 Set Union In the Set Union problem we have n elements, that each are initially in n singleton sets, and we want to support the following operations: Union (A,B): Merge the two sets A and B into one new set C = AUB destroying the old sets. SameSet(x,y): Return true, if x and y are in the same set, and false otherwise. We can implement it the following way. Initially, give each set a color. When merging two sets, recolor the smallest one with the color of the larger one (break ties arbitrarily). To answer SameSet queries, check if the two elements have the same color. 4.1 Analyze the worst case cost of the two operations. 4.2 Show that the amortized cost is O(logn) for Union and O(1) for SameSet. That is, show that a any sequence of m unions and I SameSet operations takes time 0(mlogn+1). Hint: Give a bound on the number of times an element can be recolored.