Running Time Analysis

Informal potential function analysis:

• All the work is in relabeling nodes. How many times can a node u be relabeled? In particular, if u is in a set of size k, how many times could it have been relabeled?

• The final set size is |V|, so how many times can a node be relabeled?

• Thus, $\Theta(\vert V\vert \log \vert V\vert)$ time for all calls to JOIN, since all |V| nodes end up in sets of size |V|. This is dominated by the time to sort, so no further improvements to JOIN and CONNECTED will help!

Total: SORT plus JOIN is $O(\vert E\vert\log\vert E\vert) = O(\vert E\vert\log\vert V\vert)$.