1,270 views
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?

1 Answer

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.

 

edited by

Related questions

0 votes
0 votes
2 answers
2
manvi_agarwal asked Aug 10, 2018
1,663 views
Solution using back substitution methodT(n) = 2T(n/2) + nlogn ?detailed solution please.ans is nlognlogn or n(logn)^2
0 votes
0 votes
1 answer
3
Rahul Ranjan 1 asked Aug 6, 2018
1,580 views
How can we apply Masters theorem to these equations : T(n) = 16*T(n/4) + n!and T(n) = 4*T(n/2) + cnPlease explain the process.
0 votes
0 votes
1 answer
4
bts asked Jul 17, 2018
540 views
Solve by using master's theorem