Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $
Let us assume that $n$ is of the form $2^{2^k}$, and furthermore, a base case of $T(2) = 1$. Applying the substitution method,
\begin{align}
T(2^{2^k}) &amp;= 1 + 2^{2^{k-1}} T(2^{2^{k-1}}) \\ &amp;=
1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) \\ &amp;=
1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} T(2^{2^{k-3}}) \\ &amp;= \cdots \\ &amp;=
1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} + \cdots + 2^{2^{k-1} + \cdots + 2^0} T(2^{2^0}) \\ &amp;=
1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} + \cdots + 2^{2^{k-1} + \cdots + 2^0} \\ &amp;=
2^{2^{k}} \left[
2^{-2^k} + 2^{-2^{k-1}} + 2^{-2^{k-2}} + 2^{-2^{k-3}} + \cdots + 2^{-2^0}
\right] \\ &amp;\approx
2^{2^k} \sum_{\ell=0}^\infty \frac{1}{2^{2^\ell}}.
\end{align}
The infinite series converges, and we conclude that $T(2^{2^k}) = \Theta(2^{2^{k}})$.