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 Satbir commented Jun 12, 2019 i edited by Satbir Jun 12, 2019 reply Follow Share The equation should be in the form of $aT(\frac{n}{b}) + O(n^{k} log^{p}n)$ where a$\geq$1 and b>1 and k$\geq$0 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 The extended 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. 2 votes 2 votes lolster commented Jun 12, 2019 reply Follow Share @Satbir Thanks for your reply. The link clarified almost all of my doubts. I am still confused regarding the violation by $T(n) = 2T(\frac{n}{2}) + \frac{n}{logn}$ Could you please clarify this? Thanks. 0 votes 0 votes Satbir commented Jun 12, 2019 reply Follow Share $T(n)= 2T\left ( \frac{n}{2} \right )+\frac{n}{log n}$ $\implies T(n)= 2T\left ( \frac{n}{2} \right )+n(logn)^{-1}$ $\implies T(n)= 2T\left ( \frac{n}{2} \right )-n(logn)$ here f(n) is not positive so we can't apply master's theorem. 0 votes 0 votes lolster commented Jun 12, 2019 reply Follow Share @Satbir $ \log(n^{-1}) = -\log n \neq (\log n)^{-1} $ 1 votes 1 votes Satbir commented Jun 12, 2019 reply Follow Share then it will can apply master theorem. a=2,b=2,k=1,p=-1 $a=b^{k}$ and p=-1 so $T(n) = \theta(n\ loglog\ n)$ 0 votes 0 votes 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.