The recurrence relation is given as follows:

$T(n) = 2T(\sqrt{n})+1$

$T(1) = 1$

I tried to solve it with recursion tree as follows: enter image description here

But to find the number of levels that may occur, I have to solve:

$\sqrt[2^x]{n} = 1$


$\log{1} = 0$

So I am stuck here and cant move further.

What I am doing wrong?

PS: I know we can solve this using master theorem. But I am specifically interested in solving this using recursion tree method.

  • $\begingroup$ To solve $\sqrt[2^x]{n}\approx1$, note that this is equivalent to $\exp((\log n)/2^x)\approx1$, thus $\log n\approx 2^x$ and $x\approx\log\log n$. $\endgroup$ – Did Jan 26 '16 at 14:39
  • $\begingroup$ Sorry didnt get $exp((\log{n})/2^x)≈1$. Is it: $\frac{\log{n}}{2^x}≈1$? $\endgroup$ – Maha Jan 26 '16 at 14:50
  • 1
    $\begingroup$ In theory one should solve $\sqrt[2^x]{n}=1$, thar is, $\exp((\log n)/2x)=1$, which has no finite solution $x$ if $n>1$. Hence the idea of the method is to estimate the number $x$ of steps needed to make $\sqrt[2^x]{n}$ smaller than any finite fixed level $>1$, say, the smallest integer $x$ such that $\sqrt[2^x]{n}<2$. Rigorously speaking, this is the smallest $x$ such that $2^x>\log_2n$, thus $x$ is indeed of order $\log\log n$. $\endgroup$ – Did Jan 26 '16 at 14:55
  • $\begingroup$ facing my inexperience with maths. I dont get how is $\sqrt[2^x]{n} = exp((\log{n})/2x)$. Facing this first time. Not aware of $exp((\log{n})/2x)$. Can you explain or give me some link about what does this means? $\endgroup$ – Maha Jan 26 '16 at 15:02
  • $\begingroup$ Sorry, typo (but the first time was correct), in fact $\sqrt[2^x]{n}=\exp((\log n)/2^x)$, always. Note that $n=\exp(\log n)$ and that $\sqrt[2^x]{k}=k^{1/2^x}$ hence $\sqrt[2^x]{n}=(\exp(\log n))^{1/2^x}=\exp((\log n)/2^x)$. $\endgroup$ – Did Jan 26 '16 at 15:05

You are looking at this recurrence relation:

$T(n) = 2T(\sqrt{n})+1$

$T(1) = 1$

Suppose T is a solution. Then we have $T(1) = 2T(1) + 1$, so $1 = 3$. That is, this recurrence relation has no solution.


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.