Average case running time of quick sort
It suffices to show that Quicksort runs in time $f(n) = O(n^2)$ in the worst case, since this immediately implies that it also runs in at most $f(n)$ time on average.
The recurrence equation that describes the worst-case running time for Quicksort is
$$
T(n) = T(n-1) + \Theta(n),
$$
which has solution $T(n) = \Theta(n^2)$.