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$ May 6, 2014 at 1:37
  • 1
    $\begingroup$ Which of the steps 1–3 have you attempted? Where did you get stuck? $\endgroup$ May 6, 2014 at 1:39
  • $\begingroup$ Also, step 2 is wrong. Perhaps you meant something else. $\endgroup$ May 6, 2014 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$ May 6, 2014 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, 2014 at 6:48

1 Answer 1

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$ May 6, 2014 at 3:14
  • $\begingroup$ @user2197917 Yes, that's the idea. $\endgroup$ May 6, 2014 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.