Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

up vote 1 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|improve this answer
    
Aha! Thank you. –  Michael Chen Jan 4 '12 at 0:34
add comment

Your Answer

 
discard

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.