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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.