$T(n)=n\sqrt{n}T(\sqrt{n})+n^3\log^2{(n\log{(\log{n})})}$

65 Views Asked by At

I'm trying to solve this recursion equation:

$T(n)=n\sqrt{n}T(\sqrt{n})+n^3\log^2{(n\log{(\log{n})})}$

I tried to substitute $m=\log{n}$ but it doesn't seem to help:

$T(2^m)=2^{\frac{3m}{2}}T(2^{\frac{m}{2}})+2^{3m}\log^2{(2^m\log{(m)})}$

How can I proceed from here?

1

There are 1 best solutions below

0
On

As

$$ T\left(2^{\log_2 n}\right)=n\sqrt{n}T\left(2^{\log_2 \sqrt{n}}\right)+n^3\log_2^2(n\log_2(\log_2 n)) $$

making $\mathcal{T}(\cdot)=T(2^{(\cdot)})$ and $z = \log_2 n$ we have

$$ \mathcal{T}(z)=2^z 2^{\frac z2}\mathcal{T}\left(\frac z2\right)+2^{3z}\log_2^2(2^z\log_2z) $$

now calling $\mathbb{T}(\cdot)=\mathcal{T}(2^{(\cdot)})$ and making $u = \log_2 z$ we have

$$ \mathbb{T}(u)=2^{\frac 32 2^u}\mathbb{T}(u-1)+2^{3\times 2^u}\log_2^2(2^{u}u) $$

with solution

$$ \mathbb{T}(u)=8^{2^u-2} \left(c_1+\sum _{k=1}^{u} 2^{6-2^{k}} \log_2 ^2\left(2^{k} k\right)\right) $$

finally we should return to $T(n)$ with $\mathbb{T}_u\to\mathcal{T}_z\to T_n$