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) ?
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).
I'm not familiar with d in the master theorem. The wikipedia article on the Master Theorem states that you need to find c = log_b a, the critical exponent. Here the c = 1. Case 2 requires we have f(n) = Theta(n log n), but in reality we have f(n) = log n. Instead, this problem falls into case 1 (see if you can figure out why!), which means T(n) = Theta(n), as you found elsewhere.
