Solve equation using master theorem T(n) = 8T(n/2) + 3n^2

Question

I can't figure out how to proceed and which case it's falling under after calculating h(n)

Comments

what do you mean by h(n)?

Answer 1

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/

Comments

You missed the regularity condition for case 3 :)

---

@Arjun Sir , I have edited my answer. Please let me know if it is correct now.

---

Have edited it.

---

Ok sir.