I would make a guess and then try the substitution method. I'm not very good with recurrences though so use this advice at your own risk (of failure). But the guess I'd make first would take into consideration that for large n, n/2 + root n is controlled by n/2. That square root at the end of the recurrence doesn't matter, I don't think, because it's a constant. After you make the guess though, you substitute and see if it works, so even if your logic sucks, as mine might have, as long as you can do algebra, it doesn't matter.

The Akra-Bazzi theorem ( http://en.wikipedia.org/wiki/Akra-Bazzi_method ) applies in this case because sqrt(n) is O(n/log(n)^2) so you can just use the Master theorem. So BestJewSinceJC's intuition is correct.

Try Substitution