# Logs of logs function

**URL:** <https://boards.straightdope.com/t/logs-of-logs-function/703853>\
**Category:** Factual Questions\
**Created:** [November 6, 2014, 5:16am UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853 "2014-11-06T05:16:55Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\
**Post date:** [November 6, 2014, 5:16am UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/1 "2014-11-06T05:16:55Z")

</div>

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).

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [November 6, 2014, 6:46am UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/2 "2014-11-06T06:46:40Z")

</div>

Sounds like the [iterated logarithm](http://en.wikipedia.org/wiki/Iterated_logarithm).

---

<div class="post-metadata">

**Author:** ![Jragon](https://avatars.discourse-cdn.com/v4/letter/j/e19b73/32.png) [@Jragon](https://boards.straightdope.com/u/Jragon)\
**Post date:** [November 6, 2014, 6:52am UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/3 "2014-11-06T06:52:04Z")

</div>

Ah, yes, thank you.

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.

---

<div class="post-metadata">

**Author:** ![Ignotus](https://avatars.discourse-cdn.com/v4/letter/i/ecc23a/32.png) [@Ignotus](https://boards.straightdope.com/u/Ignotus)\
**Post date:** [November 6, 2014, 7:00am UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/4 "2014-11-06T07:00:23Z")

</div>

Ever heard the old joke: what’s the sound of a drowning analythic number theorist?

(Answer: log log log log log log log log log log…)

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [November 6, 2014, 10:02pm UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/5 "2014-11-06T22:02:12Z")

</div>

> [@Jragon](#):
>
> Ah, yes, thank you.
> 
> 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.

---

<div class="post-metadata">

**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\
**Post date:** [November 6, 2014, 10:56pm UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/6 "2014-11-06T22:56:11Z")

</div>

> [@ftg](#):
>
> (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.)

Do you know the reference?

---

<div class="post-metadata">

**Author:** ![ftg](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/ftg/32/2801_2.png) [@ftg](https://boards.straightdope.com/u/ftg)\
**Post date:** [November 7, 2014, 9:24pm UTC](https://boards.straightdope.com/t/logs-of-logs-function/703853/7 "2014-11-07T21:24:01Z")

</div>

> [@ultrafilter](#):
>
> Do you know the reference?

“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.
