0
$\begingroup$

Consider the following functions:

$$f(n)=2^{\log^*n} \text{ and } g(n)=\sqrt{2}^{\log{n}}$$

Using $\log{}$ properties I think that $g(n) < f(n)$, since:

  1. $f(n)\sim n$,
  2. $g(n)\sim n^{\frac{1}{2}}$, and
  3. $n^{\frac{1}{2}}<n$.

However the book that I'm reading says otherwise.

What have I gotten wrong?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

You have gotten wrong the 1st property, that $2^{\log^*(n)} \sim ~n$. This is not the case.

The notation $\log^*(n)$ is the iterated logarithm, and the iterated logarithm grows much much slower than the logarithm, so $f$ grows much slower than linearly.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'm aware of the definition of log star, so I guess the question is don't log* and log have the same properties? because if they do then I can do this: $2^{log^*n}=n^{log^*2}=n^1=n$. $\endgroup$
    – Titan
    Jan 25, 2021 at 10:54
  • 1
    $\begingroup$ No, $2^{\log^* 100} \sim 8$, whereas $100^{\log^* 2} \sim 100$. $\endgroup$
    – Pål GD
    Jan 25, 2021 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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