Worst-case analysis: We have seen that a worst-case split at every level of recursion in quicksort produces a Θ(n2) running time, which, intuitively, is the worst-case running time of the algorithm. We now prove this assertion. Using the substitution method we can show that the running time of quicksort is O(n2). Let T (n) be the worst-case time for the procedure QUICKSORT on an input of size n. We have the recurrence