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

Question

I tried to solve the recurrence $T\left(n\right)=\sqrt{n}\cdot T\left(\sqrt{n}\right)+c\log n$ using the Master Theorem. I tried the following way:

---

$n = 2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+\log2^k$

$2^{\frac{2}{k}}\cdot T\left(2^k\right)+k$

At that point i'm stuck and not sure how to handle the $2^{\frac{2}{k}}$ before the $T\left(2^k\right)$. I would also like which more tools are open to use at this problem.

Answer 1

For $n > 0$ we have

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

calling $R(n) = \frac{T(n)}{n}$ we follow with

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

but now

$$ R\left(2^{\log_2 n}\right) = R\left(2^{\log_2 \sqrt{n}}\right)+c\frac{\ln n}{n} $$

Calling now $\mathcal{R}(\cdot) = R\left(2^{(\cdot)}\right)$ and $z = \log_2 n$ we follow with

$$ \mathcal{R}(z) = \mathcal{R}\left(\frac z2\right)+c_1 z 2^{-z} $$

now using again a transformation with $\mathbb{R}(\cdot) = \mathcal{R}\left(2^{(\cdot)}\right)$ and $\mu = \log_2 z$ we follow with the recurrence

$$ \mathbb{R}(\mu) = \mathbb{R}(\mu-1) + c_1 2^{\mu}2^{-2^{\mu}} $$

with solution

$$ \mathbb{R}(\mu) = c_0 + 2c_1\sum_{k=0}^{u-1}2^{-2^{k+1}+k} $$

now going backwards with $\mu = \log_2 z$ and $z = \log_2 n$ we arrive at

$$ T(n) = n\left(c_0+2c_1\sum_{k=0}^{\log_2(\log_2 n)-1}2^{-2^{k+1}+k}\right) $$

and certainly

$$ T(n) \ge n c_0 + c_1\log_2 n $$

Answer 2

Using the nice trick of @Cesareo, and setting $n=2^{2^m}$,

$$\frac{T(2^{2^m})}{2^{2^m}}=\frac{T\left(\sqrt{2^{2^m}}\right)}{\sqrt{2^{2^m}}}+\frac{c\log2^{2^m}}{2^{2^m}}$$ is of the form

$$S(m)=S(m-1)+c'2^{m-2^m}.$$

Then by induction,

$$S(m)=S_0+c'\sum_{k=1}^m2^{k-2^k},$$

which is

$$\frac{T(n)}{n}=S_0+c'\sum_{k=1}^{\lg\lg n}2^{k-2^k}.$$

The terms of the sum are

$$2^{-1},2^{-2},2^{-5},2^{-14},2^{-20},\cdots$$ so the sum converges very quickly and is bounded above by $0.7815$.