Question

1. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

algorithms coures

Answer 1

1. What is recurrence for worst case of QuickSort and what is the time complexity in Worst case?

algorithms coures

The worst case of Quick sort happened when

i. The pivot element always is considered as one of the corner elements in sorted array.

ii. So, in quick sort for worst case, one sub problem is chosen for size zero and other sub problem is chosen for size n-1, when total number of elements in the list is n.

So, the expression for recurrence for worst case of Quick Sort is considered as

T(n)= T(n-1)+O(n)

Or, T(n)=T(n-1)+n

Time Complexity calculation:

T(0)=T(1)= 0   (1)

T(n)=T(n-1)+n ,when n>=2                           (2)

T(n)=T(n-1)+n

       =T(n-2)+(n-1) +n

       =T(n-3) +(n-2)+(n-1)+n

In this way after k^th step

T(n)=T(n-k)+T(n-k+1)+…………+ T(n-3) +(n-2)+(n-1)+n

       

If, n-k=0, then n=k

Again as per the equation (2)

T(3)=T(2)+3

T(2)=T(1)+2

T(1)=0

T(n)=T(0)+T(1)+T(2)+T(3)+.........................+ (n-2)+(n-1)+n

        =0 + 0 + 2+3+…………………………………….+ (n-2)+(n-1)+n

         =n+(n-2)+(n-3)+……………………………….+3+2

         =n+(n-2)+(n-3)+………………………………+3+2+1 -1

         =n(n+1)/2 – 1

         =n² /2+ n/2-1

         ≈ n² /2

Which is   O(n²)

So, Time complexity in Worst case is O(n²)