Consider any sequences of m MakeSet, Union, and Find operations (of which n are MakeSets) applied to an initially empty data structure. Furthermore, all Union operations in s appear before any of the Find operations. Show that execution of stakes only O(m) time if path compression is used with or without a balanced union. (Note: what [CLRS] calls “Link”, we call “Union”. So, no path compression takes place during Union calls.)

[Hint: redefine the node groups.]