Finding asymptotic bounds for $T(n)=16n^4T(n^{\frac{1}{2}})+2n^8\log^4n$

Question

I managed to get something after some work but it doesn't feel right.

$\log$ means logarithm with base $2$.

Here is what I did:

$T(n)=16n^4T(n^{\frac{1}{2}})+2n^8\log^4n$

Substitute $m=n^4$:

$T(m^{\frac{1}{4}})=16mT(m^{\frac{1}{8}})+\frac{1}{128}m^2\log^4m$

Defining $S(m)=T(m^{\frac{1}{4}})$:

$S(m)=16mS(m^{\frac{1}{2}})+\frac{1}{128}m^2\log^4m$

Dividing by $m^2$ and defining $U(m)=\frac{S(m)}{m^2}$:

$U(m)=16U(m^{\frac{1}{2}})+\frac{1}{128}\log^4m$

It is rather easy to show that (hopefully this is correct): $U(m)=\theta(\log\log m*log^4m)$

That means that $S(m)=\theta(m^2*\log\log m*\log^4m)$

From here $T(m)=\theta(m^8*\log\log m*\log^4m)$

And finally $T(n)=\theta(n^{32}*\log\log n*\log^4n)$

I am sure there are simpler ways, but my main question is if what I did is correct, and if I made a mistake, where is it?

Answer 1

I agree with you up to the formula for $T(m)$. But I don't think you get an extra fourth power by changing letters. You already did the fourth power when you changed from $S$ to $T$.