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.


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


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


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


Not the answer you're looking for? Browse other questions tagged or ask your own question.