1

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.

John Hoffman
  • 2,734

1 Answers1

1

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.

Millardo Peacecraft
  • 1,490
  • 1
  • 12
  • 26
  • 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