No. logx n is not greater than √n.
Consider n=256
,
√n = 16
,
and
log2 256 = 8 (let us assume base x=2
, as with many of the computational problems).
In your recurrence,
T(n)= √2 T(n/2) + log(n)
a = √2, b = 2 and f(n) = log(n)
logb a = log2 √2 = 1/2.
Since log n < na, for a > 0
, We have Case 1 of Master Theorem.
There for T(n) = Θ(√n)
.