How to show that the quick-sort algorithm runs in $O(n^2)$ time on average ?
Because on average, the expected running time is in $O(n\log n)$. The algorithm should not be in exponential time.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
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)$.
It’s a trick question...
O(f(n)) doesn’t only contain functions that grow about as fast as f(n), it also contains all the functions that grow a lot slower than f(n).
So the average time for quicksort is O(n log n), but it is also O(n^2), O(n^5), O(n!) and many other functions.