2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Hey, Thanks for your answer. Could I just substitute back the $\ n $ and apply $\ log $ on both sides to get $\ \Theta(log(log(n)) $ ? $\endgroup$ – bm1125 Nov 8 '20 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.