Solve the recurrence using the Master Theorem: $T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n$

Question

I am trying to solve the recurrence: $$ T(n) = 5T\left(\frac{n}{4}\right) + n\lg \lg n. $$ I tried to apply the Master Theorem but it didn't get me anywhere: $$ a=5,\; b=4\; \text{ and } f(n) = n\lg \lg n. $$ We have $\log_b a \simeq 1.16$, but I am not understanding where this is taking me.

Answer 1

It is taking you to the first case of the Master Theorem, since $f(n)\in O(n^{c})$ for, e.g., $c=1.1 < \log_b a = \log_4 5 \simeq 1.16$. So $T(n) \in\Theta(n^{\log_4 5})$.