Solve the recurrence $\ T(n) = \sqrt{n}\cdot T(\sqrt{n}) + n\cdot \log(n) $

Question

Solve the following recurrence:

$$\ T(n) = \sqrt{n}\cdot T(\sqrt{n}) + n\cdot \log(n)$$

I tried to just unroll it to see if I can understand, but it is too complicated .

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

Not really clear how to proceed here? I also tried recurrence tree, but couldn't see a clear pattern. I've found a similar question here but I could not understand the answer

Answer 1

I find this answer much more simpler and efficient

This is my attempt:

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

First a change of variable $n = 2^k$ leading to:

$T(2^k) = 2^{k/2} T(2^{k/2}) + k 2^k$

Now a change of function: $T(2^k) = S(k)$, leading to:

$S(k) = 2^{k/2} S(k/2) + k2^k$

Unfortunately we cannot apply Master theorem on this because of the non-constant multiplier $2^{k/2}$.

Instead we have to expand this using repeated substitution:

$S(k) = 2^{k/2 + k/4 + \ldots + k/2^d}T(k/2^d) + k/2^d 2^{k/2^d} + \ldots + k2^k$

where $d$ is the depth of this tree. It is decided by the base case. You haven't mentioned a base case but assuming it's a constant, we can say $k/2^d = B$ and T(B) = C, whee $B,C$ are constants:

$S(k) = 2^{k/2 + k/4 + \ldots + k/2^d} C + k/2^d 2^{k/2^d} + \ldots + k2^k$.

The first term is 2 powered to a decaying GP series. The second term is a AGP series.

The GP series converges to $2$ (thus the $2^2C$ can be ignored for asymptotic bounds). The AGP series is equal to $(k^2)^k + 2^{k/4 - 2} k + 2^{k/2 - 1} k$.

We can now move back to the original variable $n$: $\Rightarrow ((\log n)^2)^{\log n} + 2^{(\log n)/4 - 2} \log n + 2^{(\log n)/2 - 1} \log n$

$\Rightarrow ((\log n)^{2\log n} + 2^{(\log n)/4 - \log 4} \log n + 2^{(\log \sqrt{n}) - \log 2} \log n$

$\Rightarrow ((\log n)^{2\log n} + 2^{(\log n^{1/4}/4} \log n + 2^{\log \sqrt{n}/2 } \log n$

$\Rightarrow ((\log n)^{2\log n} + n^{1/4} \log n /4 + \sqrt{n} \log n/2 $

Answer 2

The Ansatz $T(n)\sim An^p\log^qn$ gives$$An^p\log^qn=\frac{A}{2^q}n^{(p+1)/2}\log^qn+n\log n\implies A=2,\,p=q=1.$$

Answer 3

Step 1 : get rid of square root

$$T(n^2)=nT(n)+2n^2\ln(n)$$

Step 2 : get rid of $n^2$ factor

Let set $U(n)=\frac {T(n)}n$

$\require{cancel}\cancel{n^2}U(n^2)=T(n^2)=nT(n)+2n^2\ln(n)=\cancel{n^2}U(n)+2\cancel{n^2}\ln(n)$

After simplification we get $$U(n^2)=U(n)+2\ln(n)$$

Step 3 : get rid of the logarithm

Let set $V(n)=U(n)+a\ln(n)$

The idea is that $\ln(n^2)$ will transform to $2\ln(n)$

$V(n^2)=U(n^2)+a\ln(n^2)=U(n)+2\ln(n)+2a\ln(n)=V(n)+(2+a)\ln(n)$

So for $a=-2$ the logarithm disappear and $$V(n^2)=V(n)$$

Step 4 : linearize

Notice that powers transform multiplications into additions so if we set $n=2^p$ then $n^2=2^p2^p=2^{p+p}=2^{2p}$

If we do it again by setting $p=2^k$ then $2p=2^{k+1}$

Therefore let set $W(k)=V(2^{2^k})=V(2^p)=V(n)$ then we get $$W(k+1)=W(k)$$

Step 5 : solve

In this case the solve is trivial, this is just (for $c$ a random constant) $$W(k)=c$$

Step 6 : go back the chain of substitutions

$T(n)=nU(n)=n\big(V(n)+2\ln(n)\big)=n\big(W(k)+2\ln(n)\big)$

Finally $$T(n)=c\,n+2n\ln(n)$$

Answer 4

We have

$$ \frac{T(n)}{n}=\frac{T(\sqrt{n})}{\sqrt{n}}+\ln n $$

or with $\mathcal{T}(n)=\frac{T(n)}{n}$

$$ \mathcal{T}(n) = \mathcal{T}(\sqrt{n})+\ln n $$

or

$$ \mathcal{T}(e^{\ln n})=\mathcal{T}(e^{\ln \sqrt{n}})+\ln n $$

and now calling

$$ \cases { \mathtt{T}(\cdot) = \mathcal{T}\left(e^{(\cdot)}\right)\\ z = \ln n } $$

we follow with

$$ \mathtt{T}(z)=\mathtt{T}\left(\frac z2\right)+z $$

This recurrence has the solution

$$ \mathtt{T}(z) = c_1+2(z-1) $$

and now going backwards

$$ \mathcal{T}(n) = c_1+2(\ln n-1) $$

and finally

$$ T(n) = n\left(c_2+2\ln n\right) $$