the disjoint sets class slowly growing functions consider the recurrence ( tf( <= > ( in this equationt(nrepresents the number of timesstarting at nthat we must iteratively apply (nuntil we reach (or lesswe assume that (nis nicely defined function that reduces call the solution to the equation (nwe have already encountered this recurrence when analyzing binary search theref(nn/ each step halves we know that this can happen at most log times until reaches hence we have (nlog (we ignore low-order termsetc observe that in this casef (nis much less than (nfigure shows the solution for (nfor various (nin our casewe are most interested in (nlog the solution (nlogn is known as the iterated logarithm the iterated logarithmwhich represents the number of times the logarithm needs to be iteratively applied until we reach oneis very slowly growing function observe that log log log log and log but keep in mind that is , -digit number so while logn is growing functionfor all intents and purposesit is at most but we can still produce even more slowly growing functions for instanceif (nlognthen (nlog* in factwe can add stars at will to produce functions that grow slower and slower an analysis by recursive decomposition we now establish tight bound on the running time of sequence of (nunion/find operations the unions and finds may occur in any orderbut unions are done by rank and finds are done with path compression (nf (nn- - - / - / / log / logc log log log logn logn log* log* log** figure different values of the iterated function