# $T(n) = T(\sqrt{n}) + \sqrt{n}$ solving recurrence

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

I would like to try solving this recurrence in big-O/$$\Theta$$/$$\Omega$$.

My first idea was to take $$n = 2^m$$ so: $$T(2^m) = T(2^{m/2}) + 2^{m/2}$$ Which we rewrite as: $$G_2(m) = G_2(m/2) + 2^{m/2}$$ Where the Master Theorem would give us $$G_2(m) = \Theta(2^{m/2})$$, and so $$T(2^m) = \Theta(2^{m/2})$$ so $$T(n) = \Theta(n^{1/2})$$

Does that make sense? Thank you for insights on how to work through this!

Following an answer by @marty, I like to suggest a direct substitution $$T(n) = T(n^{1/2}) + n^{1/2} = T(n^{1/4}) + n^{1/2} + n^{1/4} = \ldots$$ $$= \sum\limits_{k = 1}^{\log \log n} n ^{\frac{1}{2^{k}}} \leq n^{1/2} + n^{1/4}\cdot \log\log n\leq2\,n^{1/2}$$

The lower bound is trivial (see $$n^{1/2} \leq n^{1/2} + n^{1/4} + \ldots$$), hence $$\Theta(n^{1/2})$$.

I would go up another level.

In $$T(n) = T(\sqrt{n}) + \sqrt{n}$$ let $$n = 2^{2^m}$$.

This becomes

$$\begin{array}\\ T(2^{2^m}) &= T(\sqrt{2^{2^m}}) + \sqrt{2^{2^m}}\\ &= T(2^{2^m/2}) + 2^{2^m/2}\\ &= T(2^{2^{m-1}}) + 2^{2^{m-1}}\\ \end{array}$$

Letting $$T(2^{2^m}) =U(m)$$, this becomes

$$U(m) =U(m-1)+2^{2^{m-1}}$$.

You can proceed from here, the only difficulty being $$\sum_{k=1}^m 2^{2^k}$$.

• I don't quite understand how this is an improvement over my attempted solution? Would we get a tighter bound? – rannoudanames Feb 14 '19 at 4:38
• The recursion is simpler. – marty cohen Feb 14 '19 at 6:01
• the sum should go up to $m-1$. Otherwise you get different complexity! And the sum is not really a difficulty, since $n^{1/2} >> n^{1/4}$. – dEmigOd Feb 14 '19 at 7:03