chap internal sorting happens at each partition stepthen the total cost of the algorithm will be th( = in the worst casequicksort is th( this is terribleno better than bubble sort when will this worst case occuronly when each pivot yields bad partitioning of the array if the pivot values are selected at randomthen this is extremely unlikely to happen when selecting the middle position of the current subarrayit is still unlikely to happen it does not take many good partitionings for quicksort to work fairly well quicksort' best case occurs when findpivot always breaks the array into two equal halves quicksort repeatedly splits the array into smaller partitionsas shown in figure in the best casethe result will be log levels of partitionswith the top level having one array of size nthe second level two arrays of size / the next with four arrays of size / and so on thusat each levelall partition steps for that level do total of workfor an overall cost of log work when quicksort finds perfect pivots quicksort' average-case behavior falls somewhere between the extremes of worst and best case average-case analysis considers the cost for all possible arrangements of inputsumming the costs and dividing by the number of cases we make one reasonable simplifying assumptionat each partition stepthe pivot is equally likely to end in any position in the (sortedarray in other wordsthe pivot is equally likely to break an array into partitions of sizes and - or and - and so on given this assumptionthe average-case cost is computed from the following equationn- (ncn [ (kt( )] ( ( = this equation is in the form of recurrence relation recurrence relations are discussed in and and this one is solved in section this equation says that there is one chance in that the pivot breaks the array into subarrays of size and one chance in that the pivot breaks the array into subarrays of size and and so on the expression " (kt( )is the cost for the two recursive calls to quicksort on two arrays of size and - - the worst insult that can think of for sorting algorithm