else [bcount++ [ifor bcount + [acount++ [ireturn right-bcount+ like the first partition procedurethis also achieves partitioning with the same items in the arraybut in different orderwith all items to the left of the returned pivot position smaller or equal to the pivot valueand all items to the right greater or equal to the pivot value complexity of quicksort once again we shall determine complexity based on the number of comparisons performed the partitioning step compares each of items against the pivotand therefore has complexity (nclearlysome partition and pivot choice algorithms are less efficient than otherslike partition involving more copying of items than partitionbut that does not generally affect the overall complexity class in the worst casewhen an array is partitionedwe have one empty sub-array if this happens at each stepwe apply the partitioning method to arrays of size nthen then until we reach those complexity functions then add up to ( ( ( )/ ignoring the constant factor and the non-dominant term / this shows thatin the worst casethe number of comparisons performed by quicksort is ( in the best casewhenever we partition the arraythe resulting sub-arrays will differ in size by at most one then we have comparisons in the first casetwo lots of bn/ comparisons for the two sub-arraysfour times bn/ ceight times bn/ cand so ondown to log - times bn/ log - that gives the total number of comparisons as bn/ bn/ bn/ log - bn/ log - nlog which matches the theoretical best possible time complexity of (nlog nmore interesting and important is how well quicksort does in the average case howeverthat is much harder to analyze exactly the strategy for choosing pivot at each stage affects thatthough as long as it avoids the problems outlined abovethat does not change the complexity class it also makes difference whether there can be duplicate valuesbut again that doesn' change the complexity class in the endall reasonable variations involve comparing (nitems against pivotfor each of (log nrecursionsso the total number of comparisonsand hence the overall time complexityin the average case is (nlog nlike heapsortwhen only the largest items need to be found and sortedrather than all nquicksort can be modified to result in reduced time complexity in this caseonly the first sub-array needs to be processed at each stageuntil the sub-array sizes exceed in that situationfor the best casethe total number of comparisons is reduced to bn/ bn/ bn/ mlog rendering the time complexity of the whole modified algorithm only (nfor the average casethe computation is again more difficultbut as long as the key problems outlined above are avoidedthe average-case complexity of this special case is also (