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

  • $\begingroup$ I don't quite understand how this is an improvement over my attempted solution? Would we get a tighter bound? $\endgroup$ – rannoudanames Feb 14 '19 at 4:38
  • $\begingroup$ The recursion is simpler. $\endgroup$ – marty cohen Feb 14 '19 at 6:01
  • 1
    $\begingroup$ 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}$. $\endgroup$ – dEmigOd Feb 14 '19 at 7:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.