TransWikia.com

Difficulty in few steps in proof of "Amortized cost of $text{Find-Set}$ operation is $Theta(alpha(n))$"assuming union by rank, path compression

Computer Science Asked on October 21, 2021

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] &quadtext{if $x$ is a root or $rank[x]=0$ }\
(alpha(n)-level(x)).rank[x]-iter(x) &quadtext{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

One Answer

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".

Answered by vonbrand on October 21, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP