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 :-
- $f(n)=O(n^{\log_{b}a-\epsilon })$ for some constant $\epsilon >0$, then $T(n)=\Theta (n^{\log_{b}a})$.
- $f(n)=\Theta(n^{\log_{b}a })$ ,then $T(n)=\Theta (n^{\log_{b}a}\log n)$.
- $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/