Solution to T(n) = 2T(n/2) + log n

Question

So my recursive equation is T(n) = 2T(n/2) + log n

I used the master theorem and I find that a = 2, b =2 and d = 1.

which is case 2. So the solution should be O(n^1 log n) which is O(n log n)

I looked online and some found it O(n). I'm confused

Can anyone tell me how it's not O(n log n) ?

Answer 1

This should not be case 2, but case 1.

With T(n) = 2T(n/2) + log n the critical exponent of c_crit = log_2(2) = 1 as you found, I think correctly. But certainly log n is O(n^c) for some c < 1, even for all 0 < c < 1, so case 1 applies and the whole thing is O(n^c_crit) = O(n^1) = O(n).