the iterated logarithm. Lemma 1: As the find function follows the path along to the root, the rank of node it encounters is increasing. Lemma 2: A node which is root of a subtree with rank has at least nodes. Lemma 3: The maximum number of nodes of rank is at most For convenience, we define "bucket" here: a bucket is a set that contains vertices with particular ranks. We create some buckets and put vertices into the buckets according to their ranks inductively. That is, vertices with rank 0 go into the zeroth bucket, vertices with rank 1 go into the first bucket, vertices with ranks 2 and 3 go into the second bucket. If the -th bucket contains vertices with ranks from interval then the (B+1)st bucket will contain vertices with ranks from interval We can make two observations about the buckets. The total number of buckets is at most Proof: When we go from one bucket to the next, we add one more two to the power, that is, the next bucket to will be The maximum number of elements in bucket is at most Proof: The maximum number of elements in bucket is at most Let represent the list of "find" operations performed, and let Then the total cost of finds is Since each find operation makes exactly one traversal that leads to a root, we have . Also, from the bound above on the number of buckets, we have . For , suppose we are traversing an edge from to , where and have rank in the bucket and is not the root (at the time of this traversing, otherwise the traversal would be accounted for in ). Fix and consider the sequence that take the role of in different find operations. Because of path compression and not accounting for the edge to a root, this sequence contains only different nodes and because of Lemma 1 we know that the ranks of the nodes in this sequence are strictly increasing. By both of the nodes being in the bucket we can conclude that the length of the sequence (the number of times node is attached to a different root in the same bucket) is at most the number of ranks in the buckets , that is, at most Therefore, From Observations 1 and 2, we can conclude that Therefore, Applications Disjoint-set data structures model the