The thing to point out is that the $\sqrt{n}$ in the recurrence relation should be interpreted correctly - either you view $T$ as a function defined on $\mathbb{R}_{\geq 1}$, which is bounded near $1$, or you actually understand the $\sqrt{n}$ as the integral part, i.e. $[\sqrt{n}]$.
In the first case, you fix a small neighborhood of $1$ on which the function $T$ is bounded by a fixed constant, and the recurrence stops when $n$ falls into this neighborhood; in the second case, the recurrence simply stops at $n = 1$.
Here I give a solution using the first understanding:
Put $m = \log(n)$ and rewrite the relation as:
$$ S(m)=\begin{cases}\theta(1) & m = 0 \text{ (or better: $m \rightarrow 0$)};\\ S(m/2) + \theta(m) & m > 0, \end{cases} $$
where $S(m)$ is the function defined by $S(\log(n))=T(n)$.
This translates to the following: we have constants $r$, $c$, $d$, such that:
- $S(m) \leq c$ for all $0 \leq m < r$;
- $S(m) \leq S(m/2) + d \cdot m$ for all $m \geq r$.
It is then easily proved using induction that we actually have $$ S(m) \leq \max(2c/r, 2d) \cdot m $$ for all $m \geq r/2$. (First note that it is true for $m$ in the interval $[r/2, r)$, and then show that if it is true on the interval $[x/2, x)$, then it is also true on the interval $[x, 2x)$.)
So finally we get $T(n) = \theta(\log(n))$.
