How to find order of $T$ if $T(n) = 3 \cdot T(n/3) + n \cdot \log_2 \log_2 n$
I know from lecture that recurrence like $$T(n) = a \cdot T(n/b) + f(n) $$
can be approximated in use of sum for $n=b^k$: $$ T(b^k) = aT(b^{k-1}) + f(b^k) = ... = a^k T(1) + \sum_{i=0}^{k-1} a^i f(b^{k-i}) $$ In my case I got $$T(3^k) = 3^k T(1) + \sum_{i=0}^{k} 3^k \log_2 \log_2 3^i$$ But what should be done next?
I have problem with calculate that part:
$$\sum_{i=0}^{k} 3^k \log_2 \log_2 3^i = \sum_{i=1}^{k} 3^k \log_2 \log_2 3^i = 3^k \sum_{i=1}^{k} \log_2 \log_2 3^i $$
Define $u(n):=\frac{T(n)}{n\log_2\log_2n}$ so $$u(n)=u(n/3)\frac{\log_2\log_2(n/3)}{\log_2\log_2n}+1.$$Asymptotically, $\frac{\log_2\log_2(n/3)}{\log_2\log_2n}\sim1$ so $$u(n)\sim\log_3n,\,T(n)\sim n\log_3 n\cdot\log_2\log_2n.$$In big-O notation, we can simplify this to $T(n)\in O(n\ln n\cdot\ln\ln n)$.