For, this recursion, What's the time complexity?
T(n) = 3T(n/2) + O(log n)
I think I can't use the master's theorem because a = 3, b = 2 then log2(3) = 1.58 and f(n) = n^0*log(n), so c = 0 and it doesn't fulfill the 2nd form of the master's theorem where c = logb(a) because 0 != 1.58.
Then if I apply induction and I guess T(n) = O(n) then.
T(n) <= 3 * k * n/2 + log (n)
= 3kn/2 + log(n)
< kn
So T(n) would be O(n). Is that correct?