I'm working through a problem set through MIT's OpenCourseWare and am having some trouble with recurrences.
The problem is 1-2d:
Give asymptotic upper and lower bounds for $T(n)$ in each of the following recurrences. Assume that $T(n)$ is constant for $n \leq 10$. Make your bounds as tight as possible, and justify your answers.
- $T(n) = T(\sqrt{n}) + \Theta(\lg\lg n)$
The solution states:
Change of variables: Let $m = \lg n$. Recurrence becomes $S(m) = S(m/2) + \Theta (\lg m)$. Case 2 of Master Theorem applies, so $T(n) = \Theta((\lg\lg n)^2)$.
How does the given substitution lead to the new recurrence relation?