# 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}) &= 1 + 2^{2^{k-1}} T(2^{2^{k-1}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) \\ &= 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}}) \\ &= \cdots \\ &= 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}) \\ &= 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} \\ &= 2^{2^{k}} \left[ 2^{-2^k} + 2^{-2^{k-1}} + 2^{-2^{k-2}} + 2^{-2^{k-3}} + \cdots + 2^{-2^0} \right] \\ &\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}})$$.
• Hey, Thanks for your answer. Could I just substitute back the $\ n$ and apply $\ log$ on both sides to get $\ \Theta(log(log(n))$ ? – bm1125 Nov 8 '20 at 11:29