4 ms·
The iterated logarithm, a very slow-growing function, shows up naturally in algorithm analysis: https://en.wikipedia.org/wiki/Iterated_logarithm https://en.wiki
by cousin_it 10y ago
The iterated logarithm, a very slow-growing function, shows up naturally in algorithm analysis: https://en.wikipedia.org/wiki/Iterated_logarithm https://en.wikipedia.org/wiki/Iterated_logarithm. And the inverse Ackermann of course shows up in union-find.
- repsilat 10y agoIt's also worth pointing out that these functions sometimes turn up just in terms of the bounds that have been proven about algorithms -- the functions we see can reflect the kinds of analysis we can do of algorithms as much as the performance of the algorithms themselves. And we also see some very weird exponents -- the best asymptotic bound we have on a matrix multiplication algorithm is n^2.3728639.