Solving a recurrence using the Master Theorem where $f(n) = log(\log n)$

Question

I have the recurrence $$T(n) = 3\,T(n/2) + \log(\log n)$$ I take $a = 3$, $b = 2$ and $f(n) = \log(\log n)$. I also have $\log_2 3 = 1.585$.

I'm not sure how to approach a log inside of a log. Would you solve this the same way you would if $f(n) = n\log n$?

Answer 1

Expanding on Ian's hint, consider the following two recurrences: $$ \begin{align*} U(n) &= 3U(n/2) + n \\ L(n) &= 3L(n/2) \end{align*} $$ We also use the same base cases for $U(n),L(n)$ as for $T(n)$. Easy induction shows that $L(n) \leq T(n) \leq U(n)$. The Master theorem shows that $L(n) = \Omega(n^{\log_23})$ and $U(n) = O(n^{\log_23})$, so we conclude that $T(n) = \Theta(n^{\log_23})$.