Master's Theorem: Validity of Format

Question

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?

Comments

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

---

@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.

---

I was talking about master theorem only. The extended master theorem can be applied.

Answer 1

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.