how to solve T(n)=4T(√n)+3^5n with master theorem

Question

how do i apply master theorem to this?

 

 

Comments

Let ,

$n=2^{k}$

So,

$T(2^{k})=4T(2^{\frac{k}{2}})+k^{5}$

Now , Let  $T(2^{k})=S(k)$

So,

$S(k)=4S(\frac{k}{2})+k^{5}$

now using master’s theorem , we get ,

$S(k)=\Theta (k^{5})$

$T(2^{k})=\Theta (k^{5})$

$T(n)=\Theta (logn)^{5}$

Answer 1

let n = 2$^{m}$

T(2$^{m}$) = 4T(2$^{m/2}$)+(log2$^{m}$)$^{5}$

T(2$^{m}$) = 4T(2$^{m/2}$)+m$^{5}$(log2)$^{5}$

 

let S(k) = T(2$^{m}$)

Therefore S(k) = 4S(m/2) + m$^{5}$

Using the extended master theorem,

a=4,b=2,k=5,p=0

a < b$^{k}$ and p>=0

Therefore S(k) = $\Theta$(n$^{k}$log$^{p}$n) => $\Theta$(m$^{5}$)

but m = logn

Therefore T(n) = $\Theta$(logn)$^{5}$