# Solving a recurrence relation involving square roots

Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n.$$

How can I solve this recurrence relation, which involves square roots?

Dividing both sides by $$n$$ then introducing $$S(m):=\frac{T(2^n)}{2^n}$$ yields:

$$S(m)=S(m/2)+1+\frac{1}{m}$$

It follows that: $$1 And further: $$\forall k, 1 Now summing for $$k=1\dots \log(m)-1$$ gives us: $$S(m)=\Theta(\log(m))$$ And so: $$T(n)=\Theta(n\cdot\log\log n)$$

• Isn't $m=\log n$, so should the last result be $\Theta(n\log\log n)$? Oct 11 '19 at 9:06
• @xskxzr Thanks, that was also what I got before I got confused and thought $m=2^n$ Oct 11 '19 at 9:18

Suppose $$n=2^k$$. Because of $$lim_{n\to \infty}\frac{n}{\frac{n}{\log n}}=\infty$$, you can rewrite $$T(n)$$ as follow:

$$T(n)=\sqrt{n}T(\sqrt{n})+\mathcal{O}(n).$$ By substitution method: $$T(n)=\sqrt{n}T\left(\sqrt{n}\right)+\mathcal{O}(n)$$ $$=\sqrt{n}\left(\sqrt{\sqrt{n}}T\left(\sqrt{\sqrt{n}}\right)+\sqrt{n}\right)+n$$ $$\dots$$ $$=n^{\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^k}}T\left(2^{\frac{1}{2^k}}\right)+\underbrace{n+\dots+n}_{k \text{ times}}$$

So we should find the value of $$k$$ : $$2^{\frac{1}{2^k}}=1$$ $$\implies k=\log\log n$$ Therefore $$T(n)=n^{1-2^{-\log\log n}}T(1)+n\log\log n$$ $$=\Theta(n\log\log n).$$