How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$?

Question

How do we solve the recurrence $T(n) = 2T(n/3) + n^{ \log_32 }\log\log n$? Also, is it possible to solve this recurrence by the Master method?

Answer 1

Choosing $n = 3^m$ we have

$$ T(3^m)=2T(3^{m-1})+3^{m\log_3 2}\log_3(\log_3 3^m) $$

Now calling $\mathcal{T}(\cdot)=T(3^{(\cdot)})$ we follow with the recurrence

$$ \mathcal{T}(m)=2\mathcal{T}(m-1)+2^m\log_3 m $$

This recurrence has as solution

$$ \mathcal{T}(m)=2^m \left(c_0 + \log_3 (m!)\right) $$

Now, going backwards with $m = \log_3 n$ we have

$$ T(n) = 2^{\log_3 n}\left(c_0+\log_3((\log_3 n)!)\right) $$