# Which of these two functions has a higher order of growth/complexity?

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

However the book that I'm reading says otherwise.

What have I gotten wrong?

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.
• 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$. Jan 25 at 10:54
• No, $2^{\log^* 100} \sim 8$, whereas $100^{\log^* 2} \sim 100$. Jan 25 at 11:53