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


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.