1
$\begingroup$

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?

$\endgroup$

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.

1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

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