I was reading the section of data structures for disjoint sets from the text Introduction to Algorithms by Cormen et. al .I faced difficulty in understanding few steps in the proof of the lemma as given in the question title. Here we assume we follow union by rank and path compression heuristics. Before we move into our target lemma a few definitions and lemma is required as a prerequisites for the target lemma.

(Note:Below are prerequisites of the proof where I am facing difficulty ; as the proof refers to them , so I mention the below blockquote; my doubts however start after the following blockquote.)

The prerequisites:

$$level(x)=\max\{k:rank[p[x]]\geq A_k(rank[x])\}$$ $$iter(x)=\max\{i:rank[p[x]]\geq A_{level(x)}^{(i)}(rank[x])\}$$ $$\phi_q(x) = \begin{cases} \alpha(n).rank[x] &\quad\text{if $x$ is a root or $rank[x]=0$ }\\ (\alpha(n)-level(x)).rank[x]-iter(x) &\quad\text{if $x$ is not a root and $rank[x]\geq1$ }\\ \end{cases}$$

Corollary 21.5 : As we follow the path from any node toward a root, the node ranks strictly in- increase. ■

Lemma 21.9 : Let $x$ be a node that is not a root, and suppose that the $q$ th operation is either a $\text{Link}$ or $\text{Find-Set}$. Then after the $q$th operation, $\phi_q(х) \leq \phi_{q-1}(х)$. Moreover, if $rank[x] \geq 1$ and either $level(x)$ or $iter(x)$ changes due to the $q$ th operation, then $\phi_q(х) < \phi_{q-1}(х) - 1$. That is, $x$'s potential cannot increase, and if it has positive rank and either $level(x)$ or $iter(x)$ changes, then $x$'s potential drops by at least $1$.■

$$\alpha(n) : \text{Inverse of a very fast growing function $A_k(j)$}$$

Now in the proof below I marks the steps where I face problem

Lemma 21.12: The amortized cost of each $\text{Find-Set}$ operation is $\Theta(\alpha(n))$.

Proof: Suppose that the $q$ th operation is a $\text{Find-Set}$ and that the find path contains $s$ nodes. The actual cost of the $\text{Find-Set}$ operation is $O(s)$. We shall show that no node's potential increases due to the $\text{Find-Set}$ and that at least $\max\{0,s - (\alpha(n) + 2)\}$ nodes on the find path have their potential decrease by at least $1$.

To see that no node's potential increases, we first appeal to Lemma 21.9 for all nodes other than the root. If $x$ is the root, then its potential is $\alpha(n) . rank[x]$, which does not change.

Now we show that at least $\max\{0,s - (\alpha(n) + 2)\}$ nodes have their potential decrease by at least $1$. Let $x$ be a node on the find path such that $rank[x] > 0$ and $x$ is followed somewhere on the find path by another node $у$ that is not a root, where $level(y) = level(x)$ just before the $\text{Find-Set}$ operation. (Node $у$ need not immediately follow $x$ on the find path.) $\require{color}\colorbox{yellow}{All but at most $\alpha(n) + 2$ nodes on the find path satisfy these constraints on $x$.}$ $\require{color}\colorbox{yellow}{Those that do not satisfy them are the firstnode on the find path (if it has rank $0$),}$ $\require{color}\colorbox{yellow}{ the last node on the path (i.e., the root), and the last node $w$ on the path for which}$ $\require{color}\colorbox{yellow}{ $level(w) = k$, for each $k = 0,1,2,..., \alpha(n) - 1$.}$

Let us fix such a node $x$, and we shall show that $x$'s potential decreases by at least $1$. Let $k = level(x) = level(y)$. Just prior to the path compression caused by the $\text{Find-Set}$, we have

$rank[p[x]] \geq A_k^{(iter(x)}(rank[x])$ (by definition of $iter(x)$) ,

$rank[p[y]] \geq A_k(rank[y])$ (by definition of $level(y)$ ,

$rank[y] > rank[p[x]]$ (by Corollary 21.5 and because $у$ follows $x$ on the find path)

Putting these inequalities together and letting $i$ be the value of $iter(x)$ before path compression, we have

$rank[p[y]] \geq A_k(rank[y]) \geq A_k(rank[p[x]])$ (because $A_k(j)$ is strictly increasing) $> A_k(A_k^{(iter(x)}(rank[x])) = A_k^{(i+1)}(rank[x])$ .

Because path compression will make $x$ and $у$ have the same parent, we know that after path compression, $rank[p[x]] = rank[p[y]]$ and that the path compression does not decrease $rank[p[y]]$. Since $rank[x]$ does not change, after path compression we have that $\require{color}\colorbox{pink}{$rank[p[x]]\geq A_k^{(i+1)}(rank[x])$. Thus, path compression will cause either $iter(x)$ to }$ $\require{color}\colorbox{pink}{increase (to atleast $i + 1$) or $level(x)$ to increase (which occurs if $iter(x)$ increases}$ $\require{color}\colorbox{pink}{to at least $rank[x] + 1$). In either case,by Lemma 21.9, we have $\phi_q(х) \leq \phi_{q-1}(х) - 1$.}$ $\require{color}\colorbox{pink}{Hence, $x$'s potential decreases by at least $1$.}$

The amortized cost of the $\text{Find-Set}$ operation is the actual cost plus the change in potential. The actual cost is $O(s)$, and we have shown that the total potential decreases by at least $\max\{0,s - (\alpha(n) + 2)\}$. The amortized cost, therefore, is at most $O(s) — (s — (\alpha(n) + 2)) = O(s) — s + 0(\alpha(n)) = O(\alpha(n))$, since we can scale up the units of potential to dominate the constant hidden in $О (s)$. ■

In the proof above I could not get the mathematics behind the statements highlighted in yellow and pink. Can anyone help me out?

The corresponding portion of the text can be found here

  • $\begingroup$ please can anyone help me out? If the question lacks clarity then please do say me, then I shall rectify it... $\endgroup$ Jul 20, 2020 at 15:47

1 Answer 1


Best analysis I've seen is by Seidel and Sharir "Top-Down Analysis of Path Compression" (SIAM J. Computing 34:3, 515-525 (2005). Still heavy going...

Easier to digest is Ericson's chapter in his "Algorithms".

  • $\begingroup$ the first paper by Seidel and Sharir is free I guess? I mean I cannot just read it without making a payment... $\endgroup$ Jul 22, 2020 at 20:35
  • $\begingroup$ thank you for referring me the text by Jeff Ericson. From the amazon reviews I feel it is gonna be a great parallel follow for CLRS. The reviews say that the book is excellent... Definitely I plan to go through the entire book...and the chapter you shared in particular $\endgroup$ Jul 22, 2020 at 20:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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