Algorithms: Master Method Testbook

Question

Answer 1

T(n) = 10T(n/2) + 100n³

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

Here  a > b^k 

^{So According to Masters theorem (Rule 1)-}

T(n) = $\theta$( n^log_ba  )

            = $\theta$( n^log₂10)

         =  $\theta$(n³).           ( log₂10 >3)

Ans- A

         

Comments

so 2^10=.2^(2^3.2)(that is greater than 3

            =n^3.2  > f(n)

so it will be ⦶(n^3)