Master Theorem for Solving $T(n) = T(\sqrt n) + \Theta(\lg\lg  n)$ I'm trying to solve the recurrence relation: 
$$T(n) = T(\sqrt n) + \Theta(\lg \lg n)$$
My first step was to let $m = \lg n$, making the above:
$$T(2^m) = T(2^{m\cdot 1/2}) + \Theta(\lg m)$$
If $S(m) = T(2^m)$, then
$$S(m) = S(m/2) + \Theta(\lg m)$$
This is an easier recurrence to solve.  If I try and use the Master Theorem, I calculate $n^{\log_b a}$ where $a=1$ and $b=2$ to be $n^0=1$.  It seems like this might be case 2 of the Master Theorem where $f(n)= \Theta(n^{\log_b a})$.  
For $S(m)$, $\Theta(n^{\log_b a})= \Theta(1)$.  But $f(m) = \lg m$.  Therefore $f(n) \neq \Theta(n^{\log_b a})$.  So it doesn't seem case 2 applies. 
If I use case 1 or 3 of the Master Theorem, I have to be sure that $f(n)$ is polynomially smaller or larger than $n^{log_b{a}}$, that is to say $f(n)/n^{\log_b a} \le n^\varepsilon $ for some $\varepsilon > 0$.  However, $\lg m/1$ does not meet this requirement either.
There's a solution posted to this problem on the MIT OpenCourseWare website that claims that you may use case-2 of the Master's Theorem.  It's
(http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf) as problem 1-2d.
I don't see how the Master Theorem applies to the recurrence $S(m)$.  In fact I'm not comfortable with this definition of "polynomially" larger, since traditionally polynomials must have integer exponents.  If anyone could shed some light on the matter it would be greatly appreciated!
Thanks!
 A: Starting where you left off:
$S(m)=S(m/2)+ \Theta(\lg m)$
Compared this to the generic recurrence:
$T(n) = aT(n/b) + f(n)$
Let's address the questions, you raised.
What does "polynomially" larger mean?
A function $f(n)$ is polynomially larger than another function $g(n)$, if $f(n) = n^i g(n)/t(n)$, where $t(n)$ is some sub-polynomial factor such as $\log n$, etc that appears in $g(n)$. In other words, we want to see, ignoring sub-polynomial and constant factors, if $f(n)$ is a polynomial multiple of $g(n)$.
Does case 2 apply here?
Recall that Case 2 of the master theorem applies when $f(n)$ is roughly proportional to $n^{\log_b a}\log^kn$ for some $k \ge 0$. Now, applying all this to your equation above, $a = 1$, $b=2$ and $f(m) = \Theta(\log m)$. This give $k = 1$ and since $m^{\log_2 2^0}\log^km = \Theta(\log m)$, case 2 does apply.
What is the solution using Case 2?
Generally, when case 2 does apply, the solution is always of the form $\Theta(n^{\log_b a}\log^{k+1}n)$. So, in your case, it'll be $\Theta(\log^2 m)$ as you've already figured.
A: Another iteration of your transformation should do it.  Let $p=\mathrm{lg}\ m$, $m=2^p$, and $R(p) = S(2^p)$; then the recurrence becomes $R(p) = R(p-1)+\Theta(p)$.  Can you work the rest of it from here?
