in the same set end if // If necessary, rename variables to ensure that // x has rank at least as large as that of y if x.rank < y.rank then (x, y) := (y, x) end if // Make x the new root y.parent := x // If necessary, increment the rank of x if x.rank = y.rank then x.rank := x.rank + 1 end if end function It can be shown that every node has rank or less. Consequently each rank can be stored in bits and all the ranks can be stored in bits. This makes the ranks an asymptotically negligible portion of the forest's size. It is clear from the above implementations that the size and rank of a node do not matter unless a node is the root of a tree. Once a node becomes a child, its size and rank are never accessed again. Time complexity A disjoint-set forest implementation in which Find does not update parent pointers, and in which Union does not attempt to control tree heights, can have trees with height . In such a situation, the Find and Union operations require time. If an implementation uses path compression alone, then a sequence of MakeSet operations, followed by up to Union operations and Find operations, has a worst-case running time of . Using union by rank, but without updating parent pointers during Find, gives a running time of for operations of any type, up to of which are MakeSet operations. The combination of path compression, splitting, or halving, with union by size or by rank, reduces the running time for operations of any type, up to of which are MakeSet operations, to . This makes the amortized running time of each operation . This is asymptotically optimal, meaning that every disjoint set data structure must use amortized time per operation. Here, the function is the inverse Ackermann function. The inverse Ackermann function grows extraordinarily slowly, so this factor is or less for any that can actually be written in the physical universe. This makes disjoint-set operations practically amortized constant time. Proof of O(m log* n) time complexity of Union-Find The precise analysis of the performance of a disjoint-set forest is somewhat intricate. However, there is a much simpler analysis that proves that the amortized time for any Find or Union operations on a disjoint-set forest containing objects is , where denotes