T(n) = 2T (sqrt(n))+ log n Recurrence

Question

I am aware that the question is asked before but i there is still a confusing part for me.

In book the solution is like that:

1. $T(n) = 2T(\sqrt{n}) + \log(n)$

2. $m = \log n$ yields

3. $T(2^m) = 2T(2^{m/2}) + m$

4. Then $S(m) = T(2^m)$ produces the recurrence:

5. $S(m) = 2S(m/2) + m$

6. So $T(n) = T(2^m) = S(m) = O(m\log m) = O(\log n (\log {\log n}))$

But i can't understand in part $5$, how $2T(2^{m/2})$ is converted to $2S(2m/2)$ ? If $S(m)$ is $T(2^m)$, then $S(m/2)$ must be $T(2^{m-1})$? Can you verify me that why the book's solution is correct, and i am wrong?

Answer 1

We define $S(m)$ to be $T(2^m)$, for every possible value of $m$. Changing the name of the variable, $S(M) = T(2^M)$ for every value of $M$. Substituting $M := m/2$, we get $S(m/2) = T(2^{m/2})$.

As an example, suppose that $T$ is the identity function: $T(n) = n$. We define $S(m) = T(2^m) = 2^m$. Then $S(m/2) = 2^{m/2}$.