# Is this a special case of a recurrence where the Master Method is not applicable?

So in an exam, this was the recurrence: $$T(n) = 2T(n/2) + n log(n) -n + O(log(n))$$ $$T(1) = 1$$ Why does the master method not apply here? I think it is indeed int he form $$aT(n/b) + f(n)$$ You can say: $$a =2$$ $$b = 2$$ $$f(n) = n log(n) - n + O(log(n))$$

My guess: $$O(log(n))$$ is too broad and cannot work for the master method. If it was instead $$\Theta(log(n))$$ it might have workd, i.e., if it was a tight bound, all possible function under it would be ok. But because it's an upper bound, you can have various different function and perhaps there is one which is not allowed. Still, if someone has a better answer of why this is not a recurrene where the master metod is applicable, please answer.

• "Why does the master method not apply here?" - What makes you think it doesn't? Commented Feb 16 at 15:22
• It was an exam question and according to them it doesn't apply, lol. Commented Feb 17 at 10:23