Solving a recurrence relation involving square roots

Question

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?

Answer 1

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<S(m)-S(m/2)\leq 2$$ And further: $$\forall k, 1<S(m/2^k)-S(m/2^{k+1})\leq 2$$ 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)$$

Answer 2

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