2 ms·
The disjoint set is one of my favorite data structures because the amortized running time of its basic operations is O(α(n)), α being the inverse of the Ackerma
by baddox 16y ago
The disjoint set is one of my favorite data structures because the amortized running time of its basic operations is O(α(n)), α being the inverse of the Ackermann function.
The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe), so its inverse grows extremely slowly. In fact, α(x) is less than 5 for "reasonable" values of x such as the number of atoms in the universe. Therefore, the amortized run time of the disjoint set operations can be thought of as essentially constant.
Also of interest to me is that the inverse Ackermann function is proven to be the asymptotically optimal run time for the disjoint set operations. I'm not equipped to understand that particular proof of asymptotic optimality, but other such proofs (like the O(n lg n) running time for comparison sort) are elegant and awesome.
- adrianN 16y ago> The Ackermann function grows extremely quickly (quicker than any primitive recursive function I believe) This is correct. It was basically invented to show that primitive recursion is not capable of computing every computable function.