# How does substituting $\log{n}$ in help me solve this recurrence?

I solved the recurrence $T(n) = T(\sqrt[4]{n}) + 1$, $T(2) = 1$ through thinking it through. $T(n) = O(\log{\log{n}})$ since the number of times we add 1 is the number of times we can take the 4th root of $n$. Assume $\log$ means base 2.

Apparently, I can systematically solve this recurrence by setting $n = \log{m}$ and substituting. Why? Can someone clarify that for me?

This isn't homework. I'm trying to develop a systematic way of solving similar recurrences.

-

If I substitute $n =$log $m$ then that implies that $m= a^n$ where $a$ is the base of your logarithm. Thus the recurrence will transform to
$$T(a^n) = T(a^{\frac{n}{4}}) +1$$
and if we then use the transformation that $S(n) = T(a^n)$ we will have a much simpler recurrence solvable by Master theorem, or unrolling etc.
Thanks, what do you mean by use the transformation that $S(n) = T(a^n)$? I know the master theorem, just not sure how it applies here. – John Hoffman Feb 23 '14 at 20:20
What I mean is that, the transformation $S(n)=T(a^n)$ will allow you to simplify the recurrence greatly and allow you to use master theorem. You'll end up with $S(m) = S(\frac{m}{4}) +1$ – Millardo Peacecraft Feb 23 '14 at 21:36