$\log^*(n)$ runtime analysis
Recall that for $k &gt; 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$.