Please solve at least 6, indicate which case of masters theorem was used and ple

Question

Please solve at least 6, indicate which case of masters theorem was used and please show all work. Problem 1 Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n s 10. Make your bounds as tight as possible, and justify your answers. (a) T(n) = 2T(n/3) + n lg n (b) T(n) 3T(n/5) +1g2n (c) T(n) = T(n/2) + 2n (d) T(n) = T(V+ (lg lg n) (e) T(n) 10T(n/3)+ 17n12 (f) T(n) = 7T(n/2)-m3 (g) T(n) = T(n/2+ + v6046 (h) T(n) T(n -2) +Ign (i) T(n) = T(n/5) + T(4n/5) + (n) (j) T(n) = Vii T(G) +100n

Explanation / Answer

Masters theorem to solve a recurrence relation of the form

T(n)=aT(n/b)+(nk logpn),a>=1,b>1,k>=0 and p is a real number

1)If a>bk ,then T(n)=(nlogba)

2)If a=bk

a)If p>-1,then T(n)=(nlogba logp+1 n)

b)If p=-1,then T(n)=(nlogba loglog n)

  c)If p<-1,then T(n)=(nlogba )

3)If a<bk

a)If p>=0,then T(n)=(nk logp n)

b)If p<0,then T(n)=(nk )

Given recurrence relations are

a)T(n)=2T(n/3)+nlogn

a=2,b=3,k=1,p=1

a<bk and p>0 then

T(n)=T(n)=(nk logp n)=T(n)=(n log n)

b)T(n)=3T(n/5)+log2n

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

a>bk then

T(n)=(nlogba) =T(n)=(nlog53)

c)This is the general case of the master theorem

if T(n)=aT(n/b)+f(n)

T(n)=(f(n))

here

a=1,b=2 (so logb a=1) and f(n)=2n. We see that

  T(n)=(2n)

d)

T(n)=T(n)+(log(log(n))

here take

n=2m,m=log(n)

we get

T(2m)=T(2m)+(log(log(2m)))=T(2m/2))+(log(m))

this is of the form S(m)=S(m/2)+log(m)

a=1,b=2,k=0,p=1

then a>bk

T(n)=(mlog21×(logm)2)=((loglogn)2)

e)

T(n)=10T(n/3)+17n1.2

a=10,b=3,k=1.2,p=0

a>bk then

T(n)=(nlogba) =T(n)=(nlog310)

f)

T(n)=7T(n/2)+n3

a=7,b=2,k=3,p=0

a<bk and p>0 then

T(n)=T(n)=(nk logp n)=T(n)=(n3 log0 n)=(n3 )

  

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---