Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 5 / f / Solution

The displayed procedure calls Find-Set $2|E|$ times explicitly, since it tests the two endpoints of every edge. Each successful Union decreases the number of sets by one, from $|V|$ initially to $k$ finally, so there are $|V|-k$ Union calls.

These are calls at the displayed pseudocode level. If a concrete Union(u,v) implementation performs two further internal finds rather than accepting already found roots, its implementation adds $2(|V|-k)$ find invocations. Counting those separately avoids confusing the procedure's explicit call count with the implementation of a disjoint-set union operation.