Sorting Quicksort Quicksort:Time Complexity Worst Case: T(n)=maxo≤q≤n-1(T(g)+T(n-q-1)+Θ(n) Question When would the worst case happen? The pivot is always the greatest or smallest element for each recursion. Unlucky:T(n)=O(n2)for the worst case! Lucky:worst case seldom happens! MA Jun (Institute of Computer Software) Problem Solving Apil23.2020 8/40Sorting Quicksort Quicksort: Time Complexity Worst Case: T(n) = max0≤q≤n−1(T(q) + T(n − q − 1)) + Θ(n) Question : When would the worst case happen? The pivot is always the greatest or smallest element for each recursion. Unlucky: T(n) = O(n 2 ) for the worst case! Lucky: worst case seldom happens! MA Jun (Institute of Computer Software) Problem Solving April 23, 2020 8 / 40