in Algorithms
444 views
0 votes
0 votes
I can't figure out how to proceed and which case it's falling under after calculating h(n)
in Algorithms
by
444 views

1 comment

what do you mean by h(n)?
0
0

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

4 Comments

You missed the regularity condition for case 3 :)
1
1

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

0
0
Have edited it.
0
0
Ok sir.
0
0

Related questions