Recurrence relation to find time complexity.

 Q 1. Find the time complexity of given recurrence relation-

     T(n)=3T(n/3)+n^2 for n>=0 otherwise 0.

Solution:   

 Here we apply , Master's theorem ,

 Given recurrence relation T(n)=3T(n/3)+n^2

General form of master theorem can be written as

T(n)=aT(n/b)+f(n)               where f(n) is n^k log^p n

according to our question we have,

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

now, calculate log a base to b which is 1

so, log a base to b < k

so p>=-1

so we know the time complexity in this case is:

T.C. = theta(n^k log^(p+1) n)

        =theta(n^2 log n)

which is the time complexity of given recurrence relation.

   

Concept of Master's Theorem: