1(a). The textbook UF datastructures use N + O(1) or 2N + O(1) words of memory, for a structure of size N. (A word is enough memory to store one int, and the +O(1) term includes some JVM overhead to keep track of the object and array.) How much space is used by a QuickFindUF2 of size N?

1(b). Fix some item i. Argue that whenever a union operation modifies id[i], the size of is component at least doubles. Conclude that id[i] is modified O(lg N) times.

1(c). Suppose we construct a QuickFindUF2 structure of size N, and then we do some sequence of M operations (unions and finds) on it. Argue that the total running time is O(M + N lg N). Remark: Your answer here should use the previous part, and the idea is to charge the work of traversing a list to the items in that list. You only need a few sentences.

public class QuickFindUF2 private int[] id; // id[i]-component identifier f i (subset leader) private int[] size; // size[id[i]]-size of the component private int[] next; // next[i] next item in same component (circular) private int count; umber of components public QuickFindUF2 (int n) // setup n components of size one id-new int[n]; size-new int[n]; next - new int[n]; count- n; for (int i - e; i