.
of the event S: The proof is complete. Theorem For every input array of length n, the average running time of Quicksort with random pivots is O(n log n). This theorem states that for every possible array, whilst the running time of quicksort fluctuates between O(n log n) and O(n²), the best case (n