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.

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

3. 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 $$

4. 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 $$

5. 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 \\ $$

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