retagged by
2,840 views

1 Answer

2 votes
2 votes

Master theorem applies to the recurrences relation of the following form :-

$T(n)=aT(\frac{n}{b})+f(n)$

where $a\geq 1$ and $b> 1$ are constants and $f(n)$ is an asymptotically positive function.

There are 3 cases :-

  1. $f(n)=O(n^{\log_{b}a-\epsilon })$ for some constant $\epsilon >0$, then $T(n)=\Theta (n^{\log_{b}a})$.
  2. $f(n)=\Theta(n^{\log_{b}a })$ ,then $T(n)=\Theta (n^{\log_{b}a}\log n)$.
  3. $f(n)=\Omega (n^{\log_{b}a+\epsilon })$ for some constant $\epsilon >0$ and $f(n)$ satisfies regularity condition (given below), then $T(n)=\Theta (f(n))$.

Regularity condition:- $af(\frac{n}{b})\leq cf(n)$ for some $c<1$  and all sufficiently large n.

Here given equation is 

$T(n)=8T(\frac{n}{2})+3n^{2}$

So comparing with the standard relation we get, $a=8, b=2,f(n)=3n^{2}$

$n^{\log_{a}b}=n^{\log_{2}8}=n^{3}$

so it falls under case 1 as ,

$f(n)=O(n^{\log_{b}a})=O(n^{3})$ so , $T(n)=\Theta (n^{3})$.


Simple Rule is compare $f(n)$ and  $n^{\log_{b}a}$ ,

if $f(n) > n^{\log_{b}a}$  and $af(\frac{n}{b})\leq cf(n)$ for some $c<1$  and all sufficiently large n, then $T(n)=\Theta (f(n))$

if $f(n) < n^{\log_{b}a}$ then  $T(n)=\Theta(n^{\log_{b}a})$

if $f(n) = n^{\log_{b}a}$  then $T(n)=\Theta (f(n)\log n)$. 

The comparison here for $f(n)$ and $n^{\log_{b}a}$ is in terms of polynomial difference.

https://brilliant.org/wiki/master-theorem/

https://www.geeksforgeeks.org/advanced-master-theorem-for-divide-and-conquer-recurrences/

edited by

Related questions

1 votes
1 votes
2 answers
1
mdboi asked Oct 28, 2022
735 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
0 votes
0 votes
1 answer
2
lucasbbs asked Feb 28, 2022
6,573 views
How do I apply the master theorem in the above recurrence? Please give details about which case and on hiow to solve the asymptotic analysis...
1 votes
1 votes
1 answer
3
3 votes
3 votes
1 answer
4