3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Possible duplicate of Solving or approximating recurrence relations for sequences of numbers $\endgroup$ – ryan Apr 5 at 14:31
  • 1
    $\begingroup$ 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). $\endgroup$ – dkaeae Apr 5 at 14:46
  • $\begingroup$ 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. $\endgroup$ – question4567 Apr 5 at 14:53
  • $\begingroup$ @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. $\endgroup$ – ryan Apr 5 at 15:30
4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – question4567 Apr 5 at 15:54
  • $\begingroup$ 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. $\endgroup$ – ryan Apr 5 at 17:05

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.