Consider the function (n) = min {k : A k (1) lg(n + 1)}. Show that

Consider the function α′(n) = min {k : A_k(1) ≥ lg(n + 1)}. Show that α′(n) ≤ 3 for all practical values of n and, using Exercise 21.4-2, show how to modify the potential-function argument to prove that we can perform a sequence of m MAKE-SET, UNION, and FIND-SET operations, n of which are MAKE-SET operations, on a disjoint-set forest with union by rank and path compression in worst-case time O(m α′(n)).

Exercise 21.4-2

Prove that every node has rank at most ⌊lg n⌋.