Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $ $$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$
I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each 'level' has as many operations as nodes (because of only $\ 1 $ operation in each node) so in the first level it has $\ 1 $ node then $\ \sqrt{n} $ nodes then $\ \sqrt{\sqrt{n}} $ nodes and so forth to $\ n^{\frac{1}{2^k}} $ on the lowest level on the tree.
I get the same answer when unrolling it:
$\ T(n) = n^\frac{1}{2} T(n^{\frac{1}{2}}) + 1 = n^{\frac{1}{2}}(n^{\frac{1}{4}} T(n^{\frac{1}{4}}) + 1) + 1= n^{\frac{1}{2}} ( n^{\frac{1}{4}}(n^{\frac{1}{8}} T(n^{\frac{1}{8}}) + 1 ) + 1) + 1 = ...  $
But it is really inconvenient working with this form.
Also tried using substitution as mentioned here and then applying master theorem but with I can't understand how to make the transition back. Also a similar question here but no further explanations in the answers. I would rather use tree recurrence to solve it but substitution and master theorem also good.
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}})$.