Top-down Analysis of Path Compression

The union-find problem is one of the basic problems in algorithmics. Fast algorithms for its solution are taught in most basic algorithms courses. However for the fastest algorithms the analysis of their running times is usually omitted, although one typically discusses the runnig time bound itself which is expressed in terms of the extremely slowly growing, so-called \"Inverse Ackermann\" function. I will present a new, rather easy way of analyzing the running times of union-find algorithms. It is based on a relatively simple top-down approach and naturally leads to this famous \"Inverse Ackermann\" function (without ever having to talk about the Ackermann function itself).