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

Question

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

Answer 1

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

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