[prev] 26 [next]

Worst-case Running Time

Worst case for Quicksort occurs when the pivot is the unique minimum or maximum element:
  • One of the intervals low..pivot-1 and pivot+1..high is of size n-1 and the other is of size 0
    ⇒ running time is proportional to n + n-1 + … + 2 + 1
  • Hence the worst case for non-randomised Quicksort is O(n2) 

1  2  3  4  5  6


1   |   2  3  4  5  6


1   |   2   |   3  4  5  6


                ...                


1   |   2   |   3   |   4   |   5   |   6