$\text{I'm trying to solve the recurrence relation:}$
$$T(n) = T(\sqrt n) + n$$
$\text{My first step was to let $n=2^{m}$}$
$$T(2^m) = T(2^{m\cdot 1/2}) +2^{m}$$
$\text{if S(m) = $T(2^m)$ then,}$
$$S(m) = S(m/2) + 2^m$$
$\text{This is an easier recurrence to solve.}$
$\text{If I try and use the Master Theorem, I calculate $n^{\log_b a}$}$
$\text{where a=1 and b=2 to be $n^{\log_2 1}$ which gives $n^0=1$.}$
$\text{It seems like this might be case 2 of the Master Theorem where }$
$\text{ $n^{\log_b a}$<f(n),where f(n)=$2^m$}$
$\text{According to master's condition T(n)=$\theta(f(n)(logn)^k)$where $k>=0$)}$
$\text{T(n)=$\theta(2^m)$}$
$\text{so,Ans is $T(n)=\theta(n)$}$