# Recurrence $T(n) = 2T(\sqrt{n}) + \log n$ [duplicate]

So I have a question for the recurrence $T(n) = 2T(\sqrt{n}) + \log n$. We are to use substitution method to figure out the solution. This is an example problem (not a exercise problem) in my book (Introduction to Algorithms, Third Edition pg. 86). I'm having a hard time understanding how they rename $m = \log n$.

They then get the new equation $T(2^m) = 2T(2^{m/2}) + m$. I see that turning the $m = \log n$ into $2^m = 2^{\log n}$ and using the property $a^{\log b} = b^{\log a}$ so you get $2^m = n^{\log 2}$ which goes to $2^m = n$ and hence $\sqrt{n} = 2^{m/2}$.

My question is, how do you know to guess to substitute $m$ for $\log n$?

Since you know how to solve recurrence equations of the form $S(n) = \alpha S(n/\beta) + f(n)$, you want to transform the given recurrence into this form. You notice that $\log \sqrt{n} = \frac{1}{2}\log n$, so $m = \log n$ is a good substitution.
More generally, there are no rules on how to solve recurrence relations (or anything in mathematics). Having seen the Master theorem, you know what to do when you have a recurrence of the form $S(n) = \alpha S(n/\beta) + f(n)$. Having seen this example, you know (a) what to do when you have a recurrence $T(n) = \alpha T(n^\beta) + f(n)$, and (b) it is a good idea to try to reduce a general recurrence to one of the form $S(n) = \alpha S(n/\beta) + f(n)$ by using an appropriate substitution.
• They really consider a new recurrence $S(m) = T(2^m)$ which satisfies $S(m) = 2S(m/2) + m$. – Yuval Filmus Feb 23 '14 at 18:33