Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 2 down vote accepted

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})$.

share|cite|improve this answer
Aha! Thank you. – Michael Chen Jan 4 '12 at 0:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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