.
is the running time of the partition subroutine, T(n)’s are the recursive calls. We can easily see that the solution for this recurrence is Θ(n²) since, for every element in the array, the work done is in the order of Θ(n). Let’s now suppose that the ChoosePivot subroutine selects the pivot element