# Solving recurrence relation with square root by reduction

This question has already been asked, but I still cannot understand how the substitution makes sense in the recurrence equation $$T(n)=2T(\sqrt{n})+1$$

Following the logic:

1. Substitute $$n$$ for $$2^m$$. This yields the equation:

$$T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ \text{where } n = 2^m,\ m=\log_2 n$$ Great, this makes sense because we can substitute $$n$$ back in for $$2^m$$ and then we get the original equation.

1. Now we introduce a new function $$S(m)$$ and we're going to say $$S(m)$$ = $$T(2^m)$$.

2. I don't believe this implies $$m=2^m$$, because that would not make sense. So we're saying we're defining a new function $$S$$ that takes parameter $$m$$ and simply returns the function $$T$$ with parameter $$2^m$$: $$S(m) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1$$

3. Fine, but since the $$m$$ is $$S$$ has no mathematical relationship to the $$m$$ in $$T$$, I'm going to rename $$S(m)$$ to be $$S(x)$$ to avoid confusion, so: $$S(x) \rightarrow T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1$$

4. Now if we pass $$x/2$$ into $$S$$, we get: $$S(x/2) \rightarrow T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\$$

5. Using the master theorem for $$S(x/2)$$, we get $$O(\log x)$$. However, since we have no equivalence of $$x$$ and $$n$$, then how do we substitute back to get $$n$$?

So this leads me to believe there must be some mathematical relationship between $$S(m)$$ and $$T(2^m)$$. If $$2^m$$ is substituted for $$m$$, I'm going to replace $$x$$ with $$m$$ again, because it doesn't make sense to me to use the same variable in a substitution and make it confusing.

1. Therefore: $$S(x) = T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ S(x/2) = T(2^{x/2})=2T(\sqrt{2^{x/2}})+1=2T(2^{{x/2}/2})+1=2T(2^{x/4})+1 \\ \text{where } x=2^m$$
2. Now my problem with this is: If $$x=2^m$$, $$m=\log x$$, $$m$$ also equals $$\log n$$, therefore $$\log x=\log n$$, $$n=x$$.

If $$x=n$$ then $$S(x/2)=\dots=2T(2^{n/4})+1$$.

3. The master theorem says $$S(x/2) = \Theta(log_2(x))$$.

Now $$x=n$$, so $$\Theta(\log_2 x)=\Theta(\log_2 n)$$, which is the right answer for $$T(n)$$. However: $$2T(2^{n/4})+1 \neq 2T(\sqrt{n})+1.$$ So, how can we say that the Big O of $$S(x/2)$$ is equivalent to the Big O of $$T(n)$$?

I obviously know I'm wrong. But the correct answer to this problem makes the math seem "hacky" and arbitrary. I can't seem to grasp how the logic maintains its equivalence?

Can someone help me understand how my thinking is wrong? If so, is there anyway to explain this without using $$S(m)=T(2^m)$$ because in either case I don't understand what this actually means.

• Step 4 is where you go wrong. The $m$ in $S(m)$ is the same $m$ as in $T(2^m)$ in fact you have defined that $S(m) := T(2^m)$. In Step 4 you should write something like: $S(m) = T(2^m) = 2T(2^{m/2}) + 1 = 2S(m/2)+1$. Notice that you can solve $S(m) = 2S(m/2)+1$ for O(S(m)) and then since $m = log(n)$: $S(T(n))=O(S(\log n))$ Sep 13, 2021 at 2:26
• The mathematical relationship between $S(m)$ and $T(2^m)$ is: $S(m) = T(2^m)$. Sep 13, 2021 at 7:34
• Another mathematical relationship, which is quite useful here, is: $T(n) = S(\log_2 n)$. Sep 13, 2021 at 7:39
• you could simply say that T could be expressed as a fn. of m instead of as function of n where m=logn; ie T(s(m))=2T(s(m/2))+1 & s(m)= 2^m . Now you reach the solution T(s(m))= O(log(s(m)))=O(log(2^m)), you can substitute n=(2^m) getting T(n)=O(log n)
– ShAr
Sep 13, 2021 at 9:58
• I’m having trouble understanding how a we can arbitrarily decide S(m)=T(2^m) and how this then yields S(m/2) and then is somehow still equivalent to the original function Sep 13, 2021 at 14:03

Here is the logical form of the argument.

1. The starting point is a function $$T$$ defined recursively.

(Comments: (1) Your definition misses a base case; (2) If you think of the input to $$T$$ as an integer, then $$T$$ is only defined for integers of the form $$2^{2^k}$$.)

1. Using $$T$$, we define another function $$S$$ by $$S(m) = T(2^m)$$. This function satisfies the recurrence $$S(m) = 2S(m/2) + 1$$, with base case $$S(1) = T(2)$$.

(Here we assume that the input to $$S$$ is an integer; so $$S$$ is only defined for integers of the form $$2^k$$.)

1. We find the asymptotic rate of growth of $$S(m)$$ to be $$\Theta(m)$$.

(In fact, $$S(m)+1 = 2(S(m/2)+1)$$, and so $$S(m) = m(1 + S(1)) - 1$$.)

1. Since $$T(n) = S(\log_2 n)$$, we conclude that the asymptotic rate of growth of $$T(n)$$ is $$\Theta(\log n)$$.

(In fact, $$T(2^m) = m(1 + T(2)) - 1$$.)

The question is best answered with $$n=2^{2^m}$$ so that

$$T(2^{2^m})=2T(\sqrt{2^{2^m}})+1=2T(2^{2^{m-1}})+1.$$

This has the functional form

$$S(m)=2S(m-1)+1$$

and it is no big deal to find the solution of the homogeneous recurrence $$S_h(m)=c\,2^m$$ and a particular solution $$S_p(m)=-1$$.

Now,

$$S(m)=c\,2^m-1$$ is another way to write

$$T(2^{2^m})=c\,2^m-1$$ or

$$T(n)=c\,\log_2(n)-1.$$

As we can check,

$$2c\,(\log_2(\sqrt n)-1)+1=\frac22c\,\log_2(n)-2+1=c\,\log_2(n)-1.$$

The flaw in your reasoning is to think that "the $$m$$ in $$S$$ has no mathematical relationship to the $$m$$ in $$T$$". On the opposite it is the same variable, and $$S(m)=T(2^{2^m})$$ is an identity, also written $$S(\log_2(n))=T(2^n)$$ or $$S(\log_2(\log_2(n)))=T(n)$$, which does define $$S$$ uniquely in terms of $$T$$.