How does the following evaluate?

Question

We have a recurrence as follows:

$$T(n) = 2T\left(\sqrt{n}\right) + \log n$$

Renaming $m = \log n$ yields

$$T(2^m) = 2T(2^{\frac{m}{2}}) + m$$

Renaming $S(m) = T(2^m)$ new recurrence becomes:

$$S(m) = 2S\left(\frac{m}{2}\right) + m$$

How does this $T(2^{\frac{m}{2}})$ become $S\left(\frac{m}{2}\right)$?

Answer 1

you agree that $$S(m) = T(2^m)$$ now put $\frac{m}{2}$ inplace of $m$.

$$S(\frac{m}{2})=T(2^{\frac{m}{2}})$$ so what is $T(2^{\frac{m}{2}})$ now it is $S(\frac{m}{2})$ thus we can replace $T(2^{\frac{m}{2}})$ with $S(\frac{m}{2})$ right? hope it clears your doubt!