Recursion $T(n)=5T(n/4)+n^3(\log\log(n))$

Question

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?

Answer 1

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)$.

Answer 2

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} $$