Not able to understand a logarithm conversion

Question

I was going through slides of an algorithm class and came across following.

T(n) = 2T(n^(1/2)) + lg n

Rename: m = lg n => n = 2^m T (2^m) = 2T(2^(m/2)) + m

Rename: S(m) = T(2^m) S(m) = 2S(m/2) + m

Can any one explain me how did the last equation come ? I'm not able to understand how S(m/2) came. Thank you.

Answer 1

It is just an argument substitution.

You have S(m) = T(f(m)), where f(m) = 2^m. Substitute m with m/2 and you'll get

S(m/2) = T(f(m/2)), f(m/2) = 2^(m/2)

Now you may rewrite left part T(f(m/2)) = T(2^(m/2)) = S(m/2)