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

Answer 2

To solve T(n) = 2T(n/2) + lognT(n) = 2T(n/2) + log nT(n)=2T(n/2)+log⁡n using the substitution method, draw a picture of the recursion tree. The cost at each level k is 2^k \log(n / 2^k ) = 2^k (log n - k)2klog⁡(n/2k)=2klog⁡n−k.  

Adding up costs of levels from 

 k = 1 to log2n  

the total cost is approximately O(nlog⁡n)O(n \log n)O(nlog⁡n) for the first one and O(n) for the second, so final result for the equation : 2T ( n/2 ) + lognT(n) and respective complexities for the them: 
T(n) = O(nlog⁡n) 
T(n) = O(nlog n)