Recursion $T(n)=5T(n/4)+n^3(\log\log(n))$ I need help solve this:
$\log$ is in base $4$
n=4^4^k
$T(n)=5T(n/4)+n^3(\log\log(n))$
I tried to do something and I got stuck here:
$T(4^4^k)=5T(4^(4^k-1))+((4^4^k)^3)k$
how can I continue from here I don't understand can I do something with (4^4^k)^3?
 A: You used one too many
levels of exponentiating.
In my experience,
what you used is needed when
$T(\sqrt{n})$ appears.
Here's what I would do.
$T(n)=5T(n/4)+n^3(\lg\lg(n))
$.
Let
$n=4^k
$
and this becomes
$ T(4^k)=5T(4^{k-1})+({4^k})^3\lg(k)
$.
Let
$S(k)
=T(4^k)$,
and this becomes
$ S(k)=5S(k-1)+4^{3k}\lg(k)
$.
Divide by $5^k$ to get
$ \dfrac{S(k)}{5^k}
=\dfrac{S(k-1)}{5^{k-1}}+\dfrac{4^{3k}}{5^k}\lg(k)
$.
Let
$R(k)
=\dfrac{S(k)}{5^k}$
and this becomes
$R(k)
=R(k-1)+(4^3/5)^k\lg(k)
$.
You then get an
almost-geometric sum for
$R(k)$.
Using
$1 \le \lg(k)
\le \lg(n)$
you can get bounds for
$R(n)$
and then,
working backwords,
for $T(n)$.
A: Another approach
$$
T(4^{\log_4 n})-5T(4^{\log_4 \frac n4})=n^3\ln(\ln n)
$$
now calling $T'(u) = T(4^u)$ with $u=\log_4 n$ we obtain the linear recurrence
$$
T'(u)-5T'(u-1)=4^{3u}\ln(u\ln 4)
$$
with $T'(u) = T'_h(u)+T'_p(u)$ we have
$$
T'_h(u)-5T'_h(u-1)=0\\
T'_p(u)-5T'_p(u-1)=4^{3u}\ln(u\ln 4)
$$
The homogeneous has solution $T'_h(u) = C 5^{u-1}$ now making $T'_p(u) =C(u) 5^{u-1}$ and substituting we obtain the recurrence
$$
C(u)-C(u-1) = 5^{1-u}4^{3u}\ln(u\ln 4)
$$ 
then
$$
C(u) = \sum_{k=1}^u 5^{1-k}4^{3k}\ln(k\ln 4)
$$
and then
$$
T'(u) = \left(C+\sum_{k=1}^u 5^{1-k}4^{3k}\ln(k\ln 4)\right)5^{u-1}
$$
hence
$$
T(n) = \left(C+\sum_{k=1}^{\log_4 n}\left(\frac{4^3}{5}\right)^k\ln(k\ln 4)\right)n^{\log_4 5}
$$
