Cheap and Secure Web Hosting Provider : See Now

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

, ,
Problem Detail:

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$?

#### Answered By : Yuval Filmus

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.

As you get deeper into the subject (if you choose to do so), you will learn more tricks that will help you solve problems. Yet sometimes a new trick will be necessary. When all else fails, you just try a lot of things with your recurrence. Hopefully, after a while a winning direction will emerge. This is called (mathematical) research.