0 votes 0 votes How to check if a given recurrence relation is in a format that is valid to apply Master’s Theorem? Also, how to distinguish between Master’s Theorem and extended Master’s Theorem? Algorithms algorithms master-theorem time-complexity asymptotic-notation + – lolster asked Jun 12, 2019 lolster 1.3k views answer comment Share Follow See all 8 Comments See all 8 8 Comments reply Show 5 previous comments smsubham commented Jun 12, 2019 reply Follow Share For that example, f(x) isn't a polynomial function hence master theorem isn't applicable. See this: https://www.quora.com/Master-Theorem-T-n-2T-n-2-%2B-n-log-n-I-thought-the-answer-would-be-%CE%98-nlogn-but-the-solution-says-the-Master-Theorem-does-not-apply/answer/Jeff-Erickson?ch=10&share=00ec8a0b&srid=3XD8D 0 votes 0 votes Satbir commented Jun 12, 2019 i edited by Satbir Jun 12, 2019 reply Follow Share @smsubham Are you sure about that ? https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations read the about the 2nd case....I have used extended version of master theorem. 0 votes 0 votes smsubham commented Jun 12, 2019 reply Follow Share I was talking about master theorem only. The extended master theorem can be applied. 1 votes 1 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes The equation should be in the form of $aT(\frac{n}{b}) + O(n^{k} log^{p}n)$ where $a\geq1$ and $b>1$ and $k\geq0$ and $p$ is a real number. If you can convert the given recurrence relation in this form then you can apply master theorem. This version is used for divide and conquer type of problems like mergesort, quicksort etc Another version pf master theorem is used for subtract and conquer, that is when the bigger problem is like sum of smaller subproblems. it is of the form $aT(n-b) + O(n^{k})$ https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)#Inadmissible_equations The above are some cases where you can't apply master theorem. Satbir answered Jun 12, 2019 edited Jun 12, 2019 by Satbir Satbir comment Share Follow See all 0 reply Please log in or register to add a comment.