/*perform find with path compression error checks omitted again for simplicity return the set containing *int disjsets::findint ifsx return xelse return sx findsx )figure code for disjoint sets find with path compression operations requires at most ( log ntime it is still an open problem to determine what the average-case behavior is in this situation path compression is perfectly compatible with union-by-sizeand thus both routines can be implemented at the same time since doing union-by-size by itself is expected to execute sequence of operations in linear timeit is not clear that the extra pass involved in path compression is worthwhile on average indeedthis problem is still open howeveras we shall see laterthe combination of path compression and smart union rule guarantees very efficient algorithm in all cases path compression is not entirely compatible with union-by-heightbecause path compression can change the heights of the trees it is not at all clear how to recompute them efficiently the answer is do notthen the heights stored for each tree become estimated heights (sometimes known as ranks)but it turns out that union-by-rank (which is what this has now becomeis just as efficient in theory as union-by-size furthermoreheights are updated less often than sizes as with union-by-sizeit is not clear whether path compression is worthwhile on average what we will show in the next section is that with either union heuristicpath compression significantly reduces the worst-case running time worst case for union-by-rank and path compression when both heuristics are usedthe algorithm is almost linear in the worst case specificallythe time required in the worst case is (ma(mn)(provided > )where (mnis an incredibly slowly growing function that for all intents and purposes is at most for any problem instance howevera(mnis not constantso the running time is not linear in the remainder of this sectionwe first look at some very slow-growing functionsand then in sections to we establish bound on the worst case for sequence of at most unions and find operations in an -element universe in which union is by rank and finds use path compression the same bound holds if union-by-rank is replaced with union-by-size