Re:The time complexity of the libc++ deque push_front implem...
by gpderetta on Sunday November 28, 2021 @03:20PM
(#29372568)
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.
[ Parent
| on HN ]
Re:The time complexity of the libc++ deque push_front implem...
by tylerhou on Sunday November 28, 2021 @05:43PM
(#29373921)
Tarjan'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....
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.