Suppose we implement partial path compression on find(i) by making every other node on the path from i to the root link to its grandparent (where this makes sense). This is known as path halving.
a. Write a procedure to do this.
b.Prove that if path halving is performed on the finds and either union-by-height or union-by-size is used, the worst-case running time is O(Ma(M, N)).