Quick-sort (6)
In the best case, the pivot turns out to be the median value in the array. So the left and right subarrays both have length about n/2. Then steps 1.2 and 1.3 take about comps(n/2) comparisons each.
Therefore: comps(n) ? 2 comps(n/2) + n – 1 if n > 1 comps(n) = 0 if n ? 1
Solution: comps(n) ? n log2n
Best-case time complexity is O(n log n).