1
$\begingroup$

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?

1 Answers 1

2

if $m = \lg n$, then $n = 2^m$. So $T(2^m) = T(2^{m/2}) + \Theta(\log m)$. Now set $S(m) = T(2^m)$, which means $S(m/2) = T(2^{m/2})$.