98 views
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?
| 98 views
+2

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})$

The above are some cases where you can't apply master theorem.

0

@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
$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.
+1

@Satbir $\log(n^{-1}) = -\log n \neq (\log n)^{-1}$

0
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

For that example, f(x) isn't a polynomial function hence master theorem isn't applicable.

0

@smsubham

Are you sure about that ?

read the about the 2nd case....I have used extended version of master theorem.

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

+1 vote

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})$

The above are some cases where you can't apply master theorem.

by Boss (21.6k points)
edited by