T(n) = 2 T(n/4) + √n | Master Theorem | Master Method | time complexity for recurrence

                                 

                                   T(n)  = 2 T(n/4) + √n      eq.1

we solve it by Master Method

step1 . compute n^log_b^a

                        here we compare eq.1 with T(n) = aT(n/b) + f(n)

          

                        a = 2 ,b=4 , f(n) = √n

                       

                       n^log_b^a   _à  n^log₄²   _à √n

step2.  we compare  function f(n)  to n^log_b^a  

               _{here from eq.1} 

              _{f(n) =} √n

            n^log_b^a  ₌ √n

i.e   f(n)  and  n^log_b^a  _{are equal}

f(n) = θ ( n^log_b^a)

_{so case 2 of Master Method is applied} 

step3.  Time complexity for case 2 is  

T(n) =  θ (n^log_b^a _.logn)

T(n) = θ (√n logn)