Can anybody tell me what function I may be thinking of? It’s not useful to me, I’m just curious. Someone once told me about some sort of weird function. The function, which we’ll call f[sub]b/sub, was something like the number of composed log[sub]b[/sub]s needed to get 1. So f[sub]2/sub = 3. (16 = 2^4 -> 4 = 2^2 -> 2 = 2^1 -> 1)
I’m not sure that’s the exact behavior of the function, but I recall it being something along the lines of “the number of composed logarithms needed to <satisfy some numeric condition>”.
Searching “composed logarithms” and “logs of logs” and such isn’t yielding anything. It’s possible this is an obscure function, I think it may have been in some sort of real analysis context (which isn’t a field I’m extremely well read in).
Reading that page, now I remember, I think it was actually used in asymptotic analysis of disjoint set union-find or something, along with the inverse Ackermann.
The analysis of the running time of the standard Union-Find algorithm is indeed inverse Ackermann’s. That function (the inverse) is actually a series of functions: /2, log, log*, iterated log *, iterated … .
So log* shows up in it for certain input sizes but not overall.
(Tarjan showed that inverse Ackermann’s is also a lower bound for any Union-Find algorithm that behaves in a certain way. The upper bound was a gem, this is even more remarkable.)
Engineers say that log log x is a constant. Which it is in practice. But that’s amazingly fast growing compared to log* x.
“A class of algorithms that require nonlinear time to maintain disjoint sets,” R. E. Tarjan, Journal of Computer and System Sciences, 18, Jan 1979, pp 110-127.
The model for the lower bound are pointer machines that keep the sets disjoint. Seems overly restrictive, but a lot of models that don’t meet the requirement can be shown to have the same intrinsic features that the lower bound would apply to them.