Sorting Quicksort Quicksort:Time Complexity Question What is the time complexity of QUICKSORT? QUICKSORT(A,p,r) 1 ifp<r 2 PARTITION(A,p.r) 3 QUICKSORT(A.p.q-1) 4 QUICKSORT(A,q +1,r) The recurrence:T(n)=T(m)+T(n2)+cn where: m=9-1-p+1=q-p 2=r-(q+1)+1=r-q m+n2=r-p initially,p=1,r =n m,n2 vary and depend on q=PARTITION(A,p,r) MA Jun (Institute of Computer Software) Problem Solving Api23.2020 4/40Sorting Quicksort Quicksort: Time Complexity Question : What is the time complexity of Quicksort? The recurrence: T(n) = T(n1) + T(n2) + cn where: n1 = q − 1 − p + 1 = q − p n2 = r − (q + 1) + 1 = r − q n1 + n2 = r − p initially, p = 1,r = n n1, n2 vary and depend on q = Partition(A, p,r) MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 4 / 40