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

• Possible duplicate of Solving or approximating recurrence relations for sequences of numbers
– ryan
Apr 5 '19 at 14:31
• As an addendum to the question ryan linked to: Check the answer entitled "Domain Transformation / Change of Variables" (at the time of this comment it's the last one). Apr 5 '19 at 14:46
• I can't think of what I should change in this recurrence to make it solvable. Can you help me? I'm very new to this. Apr 5 '19 at 14:53
• @dkaeae I immediately went for that too, seems to not be super easy. See my answer below. As I mention in the answer, I think lower and upper bound the depth of the recursion tree with a simpler function would be easier.
– ryan
Apr 5 '19 at 15:30

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*}

This is not a full solution, but should get you going with what dkaeae commented above (link here).

First thing that is reasonable to try is setting $$n = 2^{2^k} + 1$$. However, after applying the $$f(n) = \sqrt{n - 1} + 2$$ in the recurrence, we get $$2^{2^{k-1}} + 2$$ which is not going to work for our function $$g(k)$$ as seen in the domain transform scheme.

Next thing that I did, was determine the base case. You can see 1, 2, and 3 will not work. Thus, we have 4 is the first value where the first application of $$f^{-1}$$ is increasing. We can get the following sequence after repeatedly applying $$f^{-1}$$:

$$\{4,\ 5,\ 10,\ 65,\ 3970,\ 15745025,\ 247905749270530,\ \ldots\}$$

What we want is a function $$g(k)$$ equivalent to the $$k$$th term in this sequence. However, plugging this sequence into OEIS or wolframalpha.com presents no results. From there I tried to see what repeated application of the function $$f(n)$$ actually did:

\begin{align*} f(n) & = \sqrt{n - 1} + 2\\ f(f(n)) & = \sqrt{\sqrt{n - 1} + 1} + 2\\ f^{(3)}(n) & = \sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 2\\ f^{(4)}(n) & = \sqrt{\sqrt{\sqrt{\sqrt{n - 1} + 1} + 1} + 1} + 2\\ \vdots & = \vdots \end{align*}

The thing to notice here is that each term we have has 2 added on to the end of it. If we can find a function $$h(k)$$ that fits $$f^{(k)}(n) - 2$$, then we know $$g(k) = h(k) + 2$$. Thus, we are now searching for the sequence above, minus 2!

$$\{2,\ 3,\ 8,\ 63,\ 3968,\ 15745023,\ 247905749270528,\ \ldots\}$$

Now when you search this sequence, something does actually turn up. See sequence A003096 from OEIS. Fortunately, there is a closed form (albeit disgusting) for this sequence.

$$h(k) = \lceil c^{2^k}\rceil \quad \text{where } c=1.2955535361865325413981559700593353\ldots$$

Disclaimer: I have no idea how this constant is derived, but this closed form will work for you.

We now know a $$g(k) = h(k) + 2 = \lceil c^{2^k}\rceil + 2$$. Now try this $$g(k)$$ with Domain Transform and you should be good to go to apply recursion tree analysis on the transformed domain.

This method will work, but I think the easier way would probably be to upper bound and lower bound the depth of the recursion tree with an easier function.

• Thanks for the answer. What do you mean by upper bounding and lower bounding the recursion tree with easier function? I should probably do that since I'm still beginner and this looks way too complicated for what we're doing. Apr 5 '19 at 15:54
• I would agree, this is probably not what your instructor had in mind. What I mean by upper and lower bounding is, you know $T(\sqrt{n-1} + 2)$ decreases at a certain rate. You can upper bound it by a function that decreases slower, because this function that decreases slower will have more recursive calls and thus it will do more "work". You can do a similar thing to lower bound it, except for a function that decreases quicker.
– ryan
Apr 5 '19 at 17:05