2
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ There are other, possibly easier functions, such as $\log \log n$. $\endgroup$ – Yuval Filmus May 6 '14 at 1:37
  • 1
    $\begingroup$ Which of the steps 1–3 have you attempted? Where did you get stuck? $\endgroup$ – Yuval Filmus May 6 '14 at 1:39
  • $\begingroup$ Also, step 2 is wrong. Perhaps you meant something else. $\endgroup$ – Yuval Filmus May 6 '14 at 1:40
  • $\begingroup$ 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. $\endgroup$ – user2197917 May 6 '14 at 3:13
  • 1
    $\begingroup$ You might have to clarify whether $\log^{k} n = \log \dots \log n$ or $\log^k n = (\log n)^k$. $\endgroup$ – Raphael May 6 '14 at 6:48
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.