Question

1. Show that the worst case of the Quicksort is Ω(n²)

Answer 1

Here is the algorithm of quick sort :

In the baove algorithm , partition takes O(n) time. After each partition, we divide our array into two part. First part contains element from p to q-1 (i.e. n-r-1 elements )and second part contains element from q+1 to r (i.e. r elements).

Therefore, we can write recurrence relation as :
T(n) =T(n-r-1) +T(r) +O(n) , where, n is the total no of elements in array.
n-r-1 is the no elements in one part after partition
   r is the no of elements in other part [ As 1 element will be at its correct position as which element partition is performed ]
   O(n) is the time required to perform partition

In worst case, there will be no element in one part whereas n-1 elements in the other part .
Therefore, T(n) =T(n-1) +T(0) +O(n)
   =T(n-1) +cn
= T (n-2) + c(n-1) +cn [ As T(n-1) =T(n-2) +c(n-1) ]
     = T (n-3) + c(n-2) +c(n-1) +cn [ As T(n-2) =T(n-3) +c(n-1) ]
= c(1) +c(2) +c(3) +.... + c(n-2) +c(n-1)+cn
= cn(n+1)/2
=O (n² )

Therefore, worst case complexity of quick sort =
Hence, proved.

Here are some examples that shows time complexity of when quick sort is applied .