Solving recurrence relation having square root
The solution is $T(n) = \Theta(n)$. It is easy to see that $T(n) = \Omega(n)$ (indeed, $T(n) \geq n$), and you can prove $T(n) = O(n)$ by induction: choose some constant $C&gt;0$. Suppose that you have shown that all small enough $n$ satisfy $T(n) \leq Cn$. Then for larger $n$,
$$ T(n) \leq 2T(\sqrt{n}) + n \leq 2C\sqrt{n} + n = \left(\frac{2C}{\sqrt{n}} + 1\right)n. $$
This is at most $Cn$ if $2C/\sqrt{n}+1 \leq C$, and in particular if $n \geq 16$ and $C \geq 1$. Therefore if we define $C = \max(1,T(1)/1,\ldots,T(15)/15)$ then the argument above shows that $T(n) \leq Cn$.