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:
- substitute nSubstitute $n$ for 2^m$2^m$. ThatThis 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):$$ T(2^m)=2T(\sqrt{2^m})+1=2T(2^{m/2})+1 \\ \text{where } n = 2^m,\ m=\log_2 n $$ 3. I don't believeGreat, this implies m=2^m because that would not makemakes 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 because we have no equivalencecan substitute $n$ back in for 'x' to 'n'$2^m$ and then how do we substitute back to get 'n'?the original equation.
Now we introduce a new function $S(m)$ and we're going to say $S(m)$ = $T(2^m)$.
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 $$
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 $$
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 \\ $$
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)$S(m)$ and T(2^m)$T(2^m)$. If 2^m$2^m$ is substituted for m$m$, I'm going to replace 'x'$x$ with m$m$ again, because it doesn't make sense to me to use the same variable in a substitution and make it confusing?.
- thereforeTherefore: $$ 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 $$$$ 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 $$
- 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 \\ $$
- If $x=2^m$, $m=\log x$, $m$ also equals $\log n$, therefore $\log x=\log n$, $n=x$.
$$ \text{the master's theorem says }S(x/2) = \Theta(log_2(x)) \\ x=n,\ so\ \Theta(log_2(x))=\Theta(log_2(n)) \\ $$ 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)$T(n)$. However: $$ 2T(2^{n/4})+1\ !=\ 2T(\sqrt{n})+1 \\ $$$$ 2T(2^{n/4})+1 \neq 2T(\sqrt{n})+1. $$ So, how can we say that the Big O of S(x/2)$S(x/2)$ is equivalent to the Big O of T(n)$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?
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)$S(m)=T(2^m)$ because in either case I don't understand what this actually means.
