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

Question

So my recursive equation is the 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 the case in 2. So your 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 the case in 2, but case 1.

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

If you want to know more about the Data Science then do check out the following 

Data Science which will help you in understanding Data Science from scratch