4 ms·
log*(x) = how many times you have to take a log before you get to 1, grows more slowly than any constant length sequence of logs, and also appears naturally in
by anonetal 12y ago
log*(x) = how many times you have to take a log before you get to 1, grows more slowly than any constant length sequence of logs, and also appears naturally in many theoretical algorithms (e.g., union-find). I suspect even that is not enough to tame Knuth's arrow notation though.
- jordigh 12y agoUnion-find's big-Oh is the inverse of the Ackermann function, which isn't quite the same as iterated logs...
- charrison 12y agoDepends on how you derive it. I've seen derivations that end up with a log* term. Of course, inverse Ackermann is a tighter bound.
- throwaway_yy2Di 12y agolog* doesn't beat Knuth arrows. See that log*(e ↑↑ n) = (n-1) log*(e) = n So log* is just the inverse of e ↑↑ n. That makes sense. Logarithm is the inverse of exponentiation. log* is iterated logartithm-ing, and (↑↑) is iterated exponentiation (aka tetration). (↑↑) builds up a stack of powers, and log* tells you how tall that stack is.