𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3 using the master theorem

Question

how do i apply master theorem to this?
 

𝑇(𝑛)=16𝑇(𝑛/4)+5𝑛^3

Comments

Compare with standard masters theorem,

$T(n)=aT(n/b)+\Theta( f(n))$

So given problem is,

$T(n)=16T(n/4)+ \Theta(n^{3})$

So, a=16, b=4.

So, $n^{\log_{b}a}=n^{\log_{4}16}=n^{2}$

So , It is the case 3 of the masters theorem where ,

$f(n)=\Omega (n^{\log_{b}a +\epsilon })$ and it holds regularity condition so ,

$T(n)=\Theta(f(n))=\Theta(n^{3})$.

Answer 1

You can apply the extended master theorem:

T(n) = aT(n/b) + $\Theta$(n$^{k}$log$^{p}$n)

as per the question :

a=16,b=4,k=3 and p=0

since a < b$^{k}$ (i.e 16 < 4$^{3}$)

p >= 0,

therefore T(n) = $\Theta$(n$^{k}$log$^{p}$n) => $\Theta$(n$^{3}$)