Can we solve this recurrence relation using recursion tree method

Question

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.

Answer 1

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.