this is a HW question so please don't just give me the answer right away. Basically, I'm working on solving the running time of this recurrence method:
$$T(n) = 4T(n/3) + n \log \log n$$
I want to try and use the master method to solve this, but somebody told me I can't, I'm not sure why. I couldn't really figure out how to use a recursion tree to solve this either (It seems to get pretty messy). Anyway, is master method a valid way to solve this problem? Thanks.
Best Answer
At least in some formulations of the Master Theorem (such as that found on Wikipedia), the relevant case for the recurrence $$ T(n) = a T(n/b) + f(n) $$ requires that $f(n)$ is $\Theta(n^c)$ for some $c<\log_b a$. And that condition is not exactly satisfied for $f(n)= n\log \log n$.
However, that difference doesn't really matter -- it's just a case of the theorem being formulated with stricter premises than necessary. In fact, if we consider the two recurrences $$ S(n) = 4(n/3) + n $$ $$ U(n) = 4(n/3) + n^{1+\varepsilon} $$ then the master theorem will apply to them and say that $S(n)$ and $U(n)$ are both $\Theta(n^{\log_3 4})$. Since we also eventually have $S(n) < T(n) < U(n)$, this bound is good for $T$ too.
So the theorem could just as well have required only that $f(n)=O(n^c)$ for some $c<\log_b a$ instead of $\Theta(n^c)$ -- and thus corrected it does indeed apply to your recurrence.