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

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.

• For starters, how did you get that? You somehow had an error while substituting since when you substitute you need to get $2^{\frac{k}{2}}T(2^{\frac{k}{2}})+k$ Jan 28, 2022 at 12:00
• Your development is meaningless, as you list unrelated expressions.
– user16034
Feb 28, 2022 at 16:13

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

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