# Can we solve this recurrence relation using recursion tree method

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:

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

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

$2x=\log{_1}{n}$

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

• 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$. – Did Jan 26 '16 at 14:39
• Sorry didnt get $exp((\log{n})/2^x)≈1$. Is it: $\frac{\log{n}}{2^x}≈1$? – Maha Jan 26 '16 at 14:50
• 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$. – Did Jan 26 '16 at 14:55
• 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? – Maha Jan 26 '16 at 15:02
• 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)$. – Did Jan 26 '16 at 15:05

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