3 ms·
Random fact of the day: The currently best known upper bound for the complexity of the Union-Find algorithm is the reverse Ackermann function, which can be trea
by gpderetta 5y ago
Random fact of the day: The currently best known upper bound for the complexity of the Union-Find algorithm is the reverse Ackermann function, which can be treated as a constant (4) for all remotely practical (and most of the impractical) values of n.
- tylerhou 5y agoTarjan's proof of inverse* Ackermann bound is hard to understand; it's much easier to understand the proof of the log*(n) bound, which is also an extremely slow growing function: https://people.eecs.berkeley.edu/~vazirani/algorithms/chap5.pdf#page=9 https://people.eecs.berkeley.edu/~vazirani/algorithms/chap5.... where log* is the iterated log function; i.e. the number of times you have to apply log repeatedly until you reach a value of 1 or smaller. For reference, log_2*(10^10000) = 5. https://en.wikipedia.org/wiki/Iterated_logarithm https://en.wikipedia.org/wiki/Iterated_logarithm