$\log^*(n)$ runtime analysis

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?

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

StackExchange Computer Science Q#1339, answer score: 14