Sample Example Solution for reference: T(n) = aT(n/b) +(n^k log^p n)

Conditions applied:

a>= 1, b>1, k>=0 and p is any real number.

1. if a>b^k , then T(n) = (n ^log_b^a)

2. if a=b^k,

a. if p> -1, then T(n) =(n ^log_b^a log ^p+1 n)

b. if p = -1, then T(n)= (n ^log_b^a log log n)

c. if p< -1, then T(n)= (n ^log_b^a)

3. if a^k,

a. if p>=0, then T(n) =(n^k log^p n)

b. if p<0, then T(n) =(n^k)

Derive the below given recursive equitation runtime T(n) using Master Theorem and justify your solution whether you can apply Master Theorem or not.

T(n)=2T(n/4)+n^0.51

T(n)=2T(n/2)+logn

T(n)=0.5T(n/2)+1/n

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

T(n)=3T(n/3)+n

T(n)=3T(n/4)+nlogn

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

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