In the most unbalanced case, each time we perform a partition we divide the list into two sublists of size 0 and n − 1 (for example, if all elements of the array are equal). This means each recursive call processes a list of size one less than the previous list. Consequently, we can make n − 1 nested calls before we reach a list of size 1. This means that the call tree is a linear chain of n − 1 nested calls. The ith call does O(n − i) work to do the partition, and \textstyle\sum_{i=0}^n (n-i) = O(n^2), so in that case Quicksort takes O(n²) time. That is the worst case: given knowledge of which comparisons are performed by the sort, there are adaptive algorithms that are effective at generating worst-case input for quicksort on-the-fly, regardless of the pivot selection strategy.[13]

      In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call  processes a list of half the size. Consequently, we can make only log₂ n nested calls before we reach a list of size 1. This means that the depth of the call tree is log₂ n. But no two calls at the same level of the call tree process the same part of the original list; thus, each level of calls needs only O(n) time all together (each call has some constant overhead, but since there are only O(n) calls at each level, this is subsumed in the O(n) factor). The result is that the algorithm uses only O(n log n) time.