5
$\begingroup$

I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set.

I was told that the potential function:

$$ \Phi(x_1, ... , x_n ) = \sum_i log(w[x_i])$$

would work (where $w[x_i]$ is the weight of the subtree rooted at $x_i$, i.e. the number of elements in the subtree rooted at $x_i$).

I was given the following argument but it doesn't quite make sense to me:

enter image description here

I can sort of see why a -1 would come in since $\frac{1}{2} = 2^{-1} \implies log(\frac{1}{2}) = -1$, but re-arranging the equation (and taking logs) gives:

$$ log(w[c]) - log(w[p]) \leq 1$$

which reverses the sign the wrong way. Plus, if you write down the details of the potential function change, things change inside the logs, which makes it tricky to analyze...

$\endgroup$
5
$\begingroup$

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of $\sqrt{n}$ finds on the bottom nodes in each list will take time $\Theta(n)$, which means that the bound of $O(m \log n)$ (here, $O(\sqrt{n} \log n)$) is incorrect. A more correct bound would be to claim that the runtime will be $O(m \log n + n)$, which accounts for the "startup cost" of doing some initially-expensive compresses.

Here's one way that you can see the runtime is $O(m \log n + n)$ without using the potential argument you mentioned in your question. Let's begin with an initial disjoint-set forest. We're going to color all the edges in the forest one of three colors: gold, blue, or red. The colors are given as follows:

  • Any edge from a node u to a node v, where the number of nodes in u's subtree is less than half the number of nodes in v's subtree, is colored blue.
  • Every other edge is red.

To understand blue and red edges, imagine that you're not going from some node up to the root, but from the root down to some node. Every time you follow a blue path, the number of nodes in the current subtree decreases by at least a factor of two. This means that if there are $n$ total nodes in the graph, any path from a node up to its root can have at most $O(\log n)$ blue edges on it, since the number of nodes in the subtree keeps dropping geometrically. That leaves red edges as everything else.

So now imagine that you start doing a find operation beginning at some node. Look at the path that you'll take up to the root. You're going to go through some number of red edges, some number of blue edges, and some number of gold edges. We don't know a priori how many red edges you'll walk through, but we can guarantee that you'll go through at most one gold edge (remember, they have to be directly pointing to the root) and at most $O(\log n)$ blue edges. This means that the cost of performing a find operation is $O(r + \log n)$, where $r$ is the total number of red edges that you pass through.

The reason that this coloring scheme is interesting is that something magic happens when you do a find. Remember, every node on the path is going to have its parent pointer changed to be the ultimate representative in the partition. Imagine that you use the potential function that you described in the question. Every time you follow a red edge (other than one that already points to the root directly), you change the node so that it points directly to the root. This means that its old parent must lose at least half the weight in its tree, which means that $\log[w_i]$ decreases by at least one. No node's weight increases, since we only move edges from descendants up to the root. This means that the drop in potential is at least $r - 1$, where $r$ is the number of red edges followed. Therefore, even though the runtime of any individual find is $O(r + \log n)$, the amortized cost of a single find is $O(\log n)$.

Now, this analysis completely ignores the costs of doing a union operation, and that's important. The good news is that it's not a problem. A union does two finds - each of which cost amortized $O(\log n)$ - and then links one tree to another. This increases the size of the root of that tree by the number of nodes in the linked tree, which is at most $n$. This means that the potential increases by at most $\log n$, so the amortized cost is $O(\log n)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.