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)

quick sort complexity analysis (best case) | best case analysis of quick sort(best case) | T(n) = 2T(n/2) + n

quick sort complexity analysis (best case)

As we  know Recurrence of  quick sort is T(n) = 2T(n/2) + 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=2 , f(n) = n

                       

               n^log_b^a     _à  n^log₂²      _à n

step2.  we compare  function f(n)  with 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.

T(n) =  θ (n^log_b^a_{.logn)                            eq.2}

_{put  value of} n^log_b^a  _à  n^log₂²  _à n   _{into eq.2}

T(n) = θ (nlogn)      Answer

Longest Common Subsequence (LCS)|Analysis of Algorithms|Algotech Programming Concept

Longest Common Subsequence (LCS)|Analysis of Algorithms|Videos

LONGEST COMMON SUBSEQUENCE (LCS)-PART-1 With Example

LONGEST COMMON SUBSEQUENCE (LCS)-PART-2 

PRINT LONGEST COMMON SUBSEQUENCE (LCS)