2
$\begingroup$

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

$\endgroup$
0
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks. I was just trying to make sure I was understanding it right and didn't see where the guess came from. Secondly, because the new T(2^m) = 2T(2^(m/2)) + m is it of form T(n)=αT(n^β)+f(n)? And if so, do I just lg(n^β) in this case so I get 2T(m/2)? $\endgroup$ – pmac89 Feb 23 '14 at 18:17
  • $\begingroup$ They really consider a new recurrence $S(m) = T(2^m)$ which satisfies $S(m) = 2S(m/2) + m$. $\endgroup$ – Yuval Filmus Feb 23 '14 at 18:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.