How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?

The recurrence I have is

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

I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm supposed to find the height of the tree but I have no idea how.

I need to solve this recurrence only using trees. And I can't find anything about solving recurrences with trees and square roots as parameters.

You could try upper and lower bounding the work done in your recurrence tree by two other simpler recurrences.

For instance, this is the function/rate by which your recurrence input decreases at each level: $$f(n) = \sqrt{n-1} + 2$$

We can find a function the decreases faster, for example

$$f_1(n) = \sqrt{n} \leq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

We can also find a function that decreases slower, for example

$$f_2(n) = 2\sqrt{n} \geq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

Thus with $f_1(n) \leq f(n) \leq f_2(n)$ we can construct two other recurrences based on these new functions:

$$\begin{align*}
T_1(n) & = 2T_1(\sqrt{n}) + 1\\
T_2(n) & = 2T_2(2\sqrt{n}) + 1\\
\end{align*}$$

We can then bound our original recurrence by these:

$$T_1(n) \leq T(n) \leq T_2(n)$$

So if you can solve these recurrences, then you can bound $T(n)$ appropriately, because these will lower bound and upper bound the depth of the recursion tree respectively.

I wanted to work through this a bit further for my own satisfaction. Not quite a recursion tree analysis, but I think this function is interesting so I worked through it.

The first $T_1$ we can solve relatively easily with a domain transform:

$$\begin{align*}
T_1(n) & = 2T_1(\sqrt{n}) + 1\\
T_1(2^{2^k}) & = 2T_1(2^{2^{k-1}}) + 1\\
S(k) & = 2S(k-1) + 1\\
& = \Theta(2^k)\\
T_1(n) & = \Theta(2^{\log \log n})\\
& = \Theta(\log n)
\end{align*}$$

The second $T_2$ is a little trickier, but not much. Let's unwrap this a bit:

$$\begin{align*}
T_2(n) &= 2T_2(2\sqrt{n}) + 1\\
&= 2\left(2T_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\
&= 4T_2(2^{3/2} \cdot n^{1/4}) + 3\\
&= 4\left(2T_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\
&= 8T_2(2^{7/4} \cdot n^{1/8}) + 7\\
&= \vdots
\end{align*}$$
The pattern starts to emerge and we can perform another domain transform (obviously, to be formal you should prove that the pattern holds by induction, but I'm omitting that).

Let $n = 4^{2^k + 1}$ and when we apply $2 \sqrt{n}$ we get:

$$\begin{align*}
2 \sqrt{4^{2^k + 1}} & = 2 \sqrt{4} \sqrt{4^{2^k}}\\
& = 4 \cdot 4^{2^{k-1}}\\
& = 4^{2^{k-1} + 1}
\end{align*}$$

Now with this we do the domain transform:
$$\begin{align*}
T_2(n) & = 2 T_2(2 \sqrt{n}) + 1 \\
T_2(4^{2^k + 1}) & = 2 T_2( 2 \sqrt{4^{2^k + 1}}) + 1\\
S(k) & = 2 S(k-1) + 1\\
& = \Theta(2^k)\\
T_2(n) & = \Theta(2^{\log_2(\log_4(n) - 1)})\\
& = \Theta(\log n)
\end{align*}$$

With this we see:

$$\begin{align*}
T_1(n) &\leq T(n) \leq T_2(n) & \forall n \geq 4\\
c_1 \log n &\leq T(n) \leq c_2 \log n & \forall n \geq 4\\
\implies T(n) & = \Theta(\log n)
\end{align*}$$

StackExchange Computer Science Q#106519, answer score: 4