7
$\begingroup$

So I know that $\log^*$ means iterated logarithm, so $\log^*(3)$ = $(\log\log\log\log...)$ until $n \leq 1$.

I'm trying to solve the following:

is

$\log^*(2^{2^n})$

little $o$, little $\omega$, or $\Theta$ of

${\log^*(n)}^2$

In terms of the interior functions, $\log^*(2^{2^n})$ is much bigger than $\log^*(n)$, but squaring the $\log^*(n)$ is throwing me off.

I know that $\log(n)^2$ is $O(n)$, but I don't think that property holds for the iterative logarithm.

I tried applying the master method, but I'm having trouble with the properties of a $\log^*(n)$ function. I tried setting n to be max (i.e. $n = 5$), but this didn't really simplify the problem.

Does anyone have any tips as to how I should approach this?

$\endgroup$
15
$\begingroup$

Recall that for $k > 1$, by definition we have $\log^*k = \log^*(\log{k}) + 1$.

By applying the definition twice, we see that $\log^*(2^{2^n}) = \log^*n + 2$. Now we can compare $\log^*n + 2$ and $(\log^*n)^2$.

$\endgroup$
2
$\begingroup$

Let's write it out and see what we get. To track the number of logs, I'll subscript them; I know that's usually base, if anyone has a better idea let me know or edit it in:

$$ \log^*(2^{2^n}) \\ = \log_1(\log_2(...\log_k(2^{2^n})...)) \\ = \log_1...\log_{k-1}(2^n\log_{k}(2)) \\ = \log_1...\log_{k-2}(\log_{k-1}(2^n)+\log_{k-1}\log_{k}(2))) \\ = \log_1...\log_{k-2}(n\log_{k-1}(2)+\log_{k-1}\log_{k}(2))) \\ \approx \log_1...\log_{k-2}(n\log_{k-1}(2)) \\ = \log_1...\log_{k-2}(n+\log_{k-1}(2)) \\ \approx \log_1...\log_{k-2}(n) \\ $$ Since we're looking for large $n$, I've dropped the additive terms $\log(\log(2))\approx-0.3665$ and $\log(2)\approx0.693$.

This shows that if $\log^*(2^{2^n}) = k$, then $log^*(n) \approx k-2$, or combining these, $$ \log^*(2^{2^n}) \approx \log^*(n)+2 $$

The big-$\Theta$s are identical, and as pointed out in the comments, if the base of the logarithm and the power are the same, the equations are identically equal.

$\endgroup$
  • 1
    $\begingroup$ By definition $\log^*n = \log^*(\log(n)) + 1$, so your result is immediate. Moreover, $\log^*(2^{2^n})$ and $\log^*(n) + 2$ are exactly equal, not just approximately. $\endgroup$ – Zach Langley Apr 18 '12 at 15:03
  • $\begingroup$ In big-theta, sure. But is there a proof of that for smaller numbers and all bases? $\endgroup$ – Kevin Apr 18 '12 at 15:16
  • $\begingroup$ Also $\log^*(\log(2^{2^n}))$ is $\log^*(2^n\log(2))$, not "exactly equal" as you say, except in base 2. $\endgroup$ – Kevin Apr 18 '12 at 15:30
  • $\begingroup$ Point taken; I was assuming logs were base 2. $\endgroup$ – Zach Langley Apr 18 '12 at 15:50
  • $\begingroup$ I understand, as I was a physics major I generally assume base $e$ unless otherwise stated. (CS too, but Physics comes first as far as logs go.) $\endgroup$ – Kevin Apr 18 '12 at 15:58

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.