1
$\begingroup$

I start off by apologizing for the fact that I don't really know how to use latex/markdown. My question, however, is directly from the Introduction To Algorithms book by Cormen et al. The topic discusses about the time analysis for disjoint set operations using forests with union-by-rank and path-compression heuristics. In particular, I am stuck at Lemma 21.13 (580) for which the "find-set(x)" subroutine is claimed to run at O(alpha(n)) time where alpha(n) is the inverse Ackermann function. I cannot arrive to the conclusion that there is at most alpha(n)+2 nodes in the find path that satisfy some specific conditions. This node count comes from the maximum number of nodes where the level(x) is constant across the find path if my interpretation is correct. I assume it is an obvious outcome of previously proven lemmas. Unfortunately, I am not so bright to validate this result.

Of course, without the details about the potential function, this question cannot be answered. There is a big problem, besides that I cannot elegantly type it out in latex. There is a ton of lemmas that logically weave this proof. So, I assume that you have the text with you. Just in case if all of this is obvious to you, here are the fundamentals.

A really really big function:
1st arg -> subscript (denotes the "level" (the notation also seems to be native within the book))
2nd arg -> superscript (denotes the number iterations of the same function)
3rd arg -> the actual input

$A(0,1, j) = j+1$
$A(k,1, j) = A(k-1,j+1,j) \mid k \ge 1$

its inverse for j = 1:
$alpha(n) = \min\{k : A(k,1,1) \ge n\}$

two auxiliary functions needed to define potential function:
//note that x is the node and x.p is its parent node, x.rank is its rank (the thing that increments monotonically traversing up)

level(x) = max {k: x.p.rank >= A(k,1,x.rank)}
iter(x) = max {i: x.p.rank >= A(level(x), i, x.rank)}

The potential function is then defined as:
//n is node count, q is the qth operation in the system, x is the node

phi(q,x) = alpha(n) * x.rank ; if x is not a root or x.rank = 0
phi(q,x) = (alpha(n) - level(x)) * x.rank - iter(x) ; if x is not a root and x.rank >= 1

Again, I emphasize that this question is really specific about the literature because it is not so obvious as to how all this and the $alpha(n)+2$ path length is necessary to prove the bound. But, I am open to other proofs where the find-set(x) subroutine (the one which compresses the path in after finding the root) is a superconstant.

$\endgroup$

1 Answer 1

1
$\begingroup$

The idea is actually quite simple. Just like in the book, let us assume that the find path consists of $s$ nodes. We disregard the root (because its potential doesn't change at all after the operation) and the node we upon which find_set is called (because it may have rank 0, which means its potential might not change). This leaves us with $s-2$ nodes.

Now, consider any node $z$ among the remaining $s-2$ nodes. As explained on pages 576-577 (I am using the 3rd edition), we have $0 \le \operatorname{level}(z) < \alpha(n)$. In other words, the level of $z$ must be between 0 and $\alpha(n) - 1$, inclusive. Indeed, it is the fact that we have a finite number of options for the levels of the aforementioned $s-2$ nodes that will help us prove the assertion presented by the authors.

They say one example is worth a thousand words, so let's do one. Suppose we have 8 nodes between the root and the one upon which find_set was called. Suppose also that $\alpha(n)$ turns out to be $4$. Here's one possibility for the levels of the nodes, given in the order they appear in the find path:

$$ 2, 0, 1, 3, 2, 3, 1, 0 $$

The book claims that there are at most $\alpha(n)$ (4 in our case) nodes $x$ for which there doesn't exist a node y later in the path such that $\operatorname{level}(x) = \operatorname{level}(y)$. Take a good look at the sequence; you'll see that the claim holds for our example.

Now, the million dollar question. Why? Think about the last $\alpha(n)$ nodes. We could assign different levels to each one (as I have done for this example) so that none of them have a complementary node higher up the find path with the same level. However, that is the most we can have; every other node will now have some ancestor with the same level. Long story short, no matter how hard we try, we cannot have more than $\alpha(n)$ nodes without an ancestor of equal level; such a scenario would require more options for the level of a node than are available.

Put it all together, and it is evident that there exists another node with the same level down the line for at least $s - \alpha(n) - 2$ of the $s$ nodes, just like the book claims.

As for why the authors have found it unnecessary to provide an explanation for their claim, you are asking the wrong guy.

$\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.