Confused about square root recurrence algorithm?

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. That yields the equation:

$$
T(2^m)=2T(sqrt{2^m})+1=2T(2^{m/2})+1 \
where n = 2^m, m=log_2(n) \
text{Great, this makes sense because we can substitute n back in for 2^m and the 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 masters theorem for S(x/2) we get O(logx). However, since we have no equivalence for ‘x’ to ‘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 \
    where x=2^m
    $$
  2. Now my problem with this is:
    $$
    if x=2^m, m=log(x), m also =log(n), therefore logx=logn, n=x \
    if x=n then S(x/2)=…=2T(2^{n/4})+1 \
    $$

$$
text{the master’s theorem says }S(x/2) = Theta(log_2(x)) \
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 != 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.