I have a homework question that asks us to show that, for size-based union-find with path compression: if all unions are done before all finds, it takes O(n) time to do O(n) unions and O(n) finds.
My thought is that if there is a way to create a lookup table to track all of the node's roots as the unions are performed, then every single union or find will take place in constant time, making the process linear. Unfortunately, I cannot find a way to make the lookup table adjustments in constant time. Any thoughts?