Big-O complexity of sqrt(n)
$\sqrt{n}$ belongs to the class of sublinear polynomials since $\sqrt{n}=n^{1/2}$.

From Wikipedia (beware of the difference between Little-o and Big-O notations):


  An algorithm is said to run in sublinear time if $T(n) = o(n)$


Note that constant factors do matter when they are part of the exponent; therefore, we can consider $O(n^{1/2})$ to be different from (and less than) $O(n)$.

With respect to the relationship between $log(n)$ and $\sqrt{n}$, you can find here a discussion about why $\log(n) = O(\sqrt{n})$.