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