2,656 views

3 Answers

Best answer
5 votes
5 votes
Extended Master Theorem:

If the recurrence is of the form $T(n)=aT(\frac{n}{b}) + \Theta (n^{k}log^{p}n) where, a\geq 1, b>1, k\geq 0$
and p is a real number.

1. if $a>b^{k}$, then T(n) = $\Theta(n^{log_{b}^{a}})$

2. if $a=b^{k}$
              a. If p > -1 then $T(n)=\Theta(n^{log_{b}^{a}} log^{p+1}n)$
              b. If p = -1 then $T(n)=\Theta(n^{log_{b}^{a}}loglogn)$
              c.  If p < -1, then $T(n)=\Theta(n^{log_{b}^{a}})$

3. If $a < b^{k}$
            a. If $p\geq 0$, then  $T(n)=\Theta(n^{k}log^{p}n)$
            b. If p < 0, then $T(n) = O(n^{k}) $
selected
0 votes
0 votes
this is the expanded version of master proof . i prefer learning it as t will be helpful in recoccurance also . and can be used in cases where normal version may not be applied. like in case of logs .

Related questions

1 votes
1 votes
1 answer
1
1 votes
1 votes
2 answers
2
mdboi asked Oct 28, 2022
736 views
how do i apply master theorem to this? T(n)=2T(n/2)−n^3n
1 votes
1 votes
1 answer
3
1 votes
1 votes
1 answer
4
ItzDc asked Jun 3, 2022
2,841 views
I can't figure out how to proceed and which case it's falling under after calculating h(n)