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

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) ?

• – greybeard Oct 27 '20 at 7:21

Mater theorem requires that $$f(n) = n^c, c\in Z$$. In your example, you cannot apply the master theorem directly. Here is my explanation for the answer. We always have $$n \geq \log n$$. Thus, $$T(\frac{n}{2}) + \log n \leq T(\frac{n}{2}) + n$$. We can apply master theorem to $$T(\frac{n}{2}) + n$$ which is $$O(n \log n)$$. This is a valid bound but not the tightest bound. If you need the tightest bound, I suggest the tree recursion method but algebra can be messy.