4
$\begingroup$

Intuitively, $\log n$ (base 2) is the number of times you have to divide $n$ by 2 before reaching a number around 2. (Waving our hands a little to gloss over floor vs ceiling and $\pm$ 1 errors.) Similarly, $\log \log n$ is the number of times we have to iterate the square root function to get from $n$ down to a number around $2$ (waving our hands again).

What is the intuition for $\log \log \log n$? What is the function that you would iterate $\log \log \log n$ times to get from $n$ down to a small constant?

  • 1
    This is not directly relevant to the question, but Joe will probably be interested to learn about [the iterated logarithm function](https://secure.wikimedia.org/wikipedia/en/wiki/Log-star), which counts the number of times one must take the logarithm of its argument before the result is less than or equal to 1.2012-07-28

2 Answers 2

3

For $\log$, you have $n \mapsto n/2$, which is really $n\mapsto\exp(\log n - 1)$, where $\exp$ is exponentiation with base $2$, i.e. $n\mapsto 2^n$ :-)

For $\log\circ\log$, you have $n\mapsto\sqrt n=\exp\big(\!\frac{\log n}2\!\big)=\exp\exp(\log\log n - 1)$.

So for $\log\circ\log\circ\log$, you'll have $n\mapsto\exp\exp\exp(\log\log\log n - 1)$, which simplifies to... $n\mapsto2^\sqrt{\log_2 n}.$ Not very pretty, I'm afraid.

Edit: In retrospect, it's kind of obvious that if you want an iteration that takes about $f(n)$ steps to reach some value, then all you need to do is decrease $f(n)$ by a fixed amount per iteration. So if the iterated function is $n \mapsto m$, you can choose $f(m) = f(n)-1$, so $m = f^{-1}(f(n)-1)$. For example, it should take about $\sqrt n$ iterations of $n\mapsto(\sqrt n-1)^2=n-2\sqrt n+1$ to map $n$ to something less than $1$.

4

Quote from Daniel Shanks:

Since $ \; \log \log \log n \rightarrow \infty \;$ (with great dignity) these inequalities imply...