# Recursion $T(n)=5T(n/4)+n^3(\log\log(n))$ [closed]

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?

## closed as off-topic by Eevee Trainer, Shailesh, YiFan, Lee David Chung Lin, GNUSupporter 8964民主女神 地下教會Apr 5 at 13:39

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Eevee Trainer, Shailesh, YiFan, Lee David Chung Lin, GNUSupporter 8964民主女神 地下教會
If this question can be reworded to fit the rules in the help center, please edit the question.

## 2 Answers

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

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