Consider the Quicksort algorithm. Suppose there is a procedure for finding a…

Key idea: the pivot splits the list so each sublist has at least n/5 elements, hence the two sublists have sizes between n/5 and 4n/5.

• Recurrence: For n larger than a constant base case, the running time satisfies T(n) <= T(n/5) + T(4n/5) + cn. The term cn (often written as +n) accounts for partitioning and pivot selection.

• Recursion-tree argument: At each level of recursion the total cost of partitioning across all subproblems is proportional to n (each element participates once per level), so the cost per level is O(n).

• Depth of the tree: The largest subproblem size shrinks by a factor of at least 4/5 each time, so the number of levels is O(log n) (specifically Theta(log_{5/4} n)).

• Total cost: Summing O(n) per level over O(log n) levels yields T(n) = Theta(n log n).

• Why other recurrences are incorrect: Forms that assume two subproblems of size n/5 or two of size 4n/5 or two of size n/2 contradict the size constraints implied by the pivot (the two parts must add to n and one side is at least n/5 while the other is at most 4n/5).