Use the Master Method to solve the following Use the Master

Use the Master Method to solve the following

Use the Master Method to solve the following three recurrence relations and state the complexity orders of the corresponding recursive algorithms. T(n) = 2T(99n/100) + 100n T(n) = 16T(n/2) + n^3 lgn T(n) = 16T(n/4) + n^2

Solution

Answer:

a) T(n) = 2T(99n/100) + 100n

   = 198T(n/100) + 100n

Using Masters theorm , we have a = 198 , b = 100 , c = 1 , f(n) = 100n

loga base b = log198 base 100 = > 1

c = 1 , since c < log a base b , T(n) = theta( n^loga base b) = theta(n)

therefore T(n) = theta(n).

b) T(n) = 16T(n/2) + n^3logn

Using Masters theorm , we have a = 16 b = 2 , c = 3 , k = 1 , loga base b = log 16 base 2 = 4

c < log a base b , therefore T(n) = theta(n^log a base b ) = theta(n^4)

Therefore , T(n) = theta(n^4)

c) T(n) = 16T(n/4) + n^2

Using Masters theorm , we have a = 16 , b = 4 , c = 2 , log a base b = loag 16 base 4 = 2

c = loga base b , therefore T(n) = theta(n^clog^k+1n) = theta(n^2logn)

Therefore , T(n) = theta(n^2logn).