Iterated logarithm $\log^* n$

I am to come up with a function based on these premise:

Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$.

The answer is the iterative logarithm $\log^* n$, and I want to show each of these steps.

1) show that $\log^* n \leq \log^{k+1} n$

2) show that $\log^{k+1} n = o(\log^k n)$

3) show that $\log^* n = \omega(1)$

I am stuck on mathematics behind these step because of my lack of knowledge of the iterated Logarithm. Can I ask for assistance at this?

• There are other, possibly easier functions, such as $\log \log n$. – Yuval Filmus May 6 '14 at 1:37
• Which of the steps 1–3 have you attempted? Where did you get stuck? – Yuval Filmus May 6 '14 at 1:39
• Also, step 2 is wrong. Perhaps you meant something else. – Yuval Filmus May 6 '14 at 1:40
• log * was a answer that some classmates and I came up for a redo chance at the problem, but it was too difficult to do. I would have not came up with log log n. – user2197917 May 6 '14 at 3:13
• You might have to clarify whether $\log^{k} n = \log \dots \log n$ or $\log^k n = (\log n)^k$. – Raphael May 6 '14 at 6:48

1 Answer

Let's assume the definition under which $\log^* 2 = 1$, $\log^* 2^2 = 2$, $\log^* 2^{2^2} = 3$, and so on. In order to show that $\log^* n = \omega(1)$, all you have to do is show that $\log^* n \to \infty$. Since $\log^*$ is increasing, it is enough to give a sequence of values $n_1,n_2,\ldots$ such that $\log^* n_i \to \infty$. Can you think of such a sequence?

In order to show that $\log^* n = o(\log^k n)$ for any fixed $k > 0$, find numbers $n_\ell$ such that $n \leq n_\ell$ implies $\log^* n \leq \ell$, and notice that for $n_{\ell-1} < n \leq n_\ell$, $\log^* n/ \log^k n \leq \ell/(\log^k n_{\ell-1})$. Perhaps you can show that $\log^k n_{\ell-1}$ is much larger than $\ell$ for large enough $\ell$. More concretely, you can try to show that $\log^k n_{\ell-1} \geq \ell^2$ (for example) for large enough $\ell$.

• Would a sequence be the 2,4,16 -> infinity? – user2197917 May 6 '14 at 3:14
• @user2197917 Yes, that's the idea. – Yuval Filmus May 6 '14 at 4:13