Question: Suppose that you implement partial path compression on find(i) by changing the parent of every other node on the path from i to the root to its grandparent (where doing so makes sense). This process is called path halving. Prove that, if path halving is performed on the finds and either union heuristic is used, the worst-case running time is still O(M log*N).