NIELIT Scientific Assistant A 2020 November: 83

Question

Which of the following is correct recurrence for worst case of QuickSort?

• A. $T(n)=T(n-4)+T(n-2)+O(1)$
• B. $T(n)=T(n-1)+T(0)+O(n)$
• C. $T(n)=2T(n/2)+O(n)$
• D. $T(n)=4T(n/2)+O(n)$

Answer 1

At first if you consider master theorem only, it may happen that option D seems to be true.

 

but recall worst case complexity of quick sort arises only when partitions are unbalanced (skewed)

therefore option B is the answer.

Answer 2

Answer is option B,

Worst case occurs in Quick sort when array is either in increasing order or in decreasing order.

Eg. Increasing : [1,2,3,4,5] , decreasing: [5,4,3,2,1]

Recurrence relation of quicksort ,

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

Case 1] Increasing order:

At that situation pivot always fall at first position of partition ,

Therefore, recurrence relation will be ,

T(n) = T(0) + T(n-1) + O(n) ... (Put k=1)

         =O(n^2)

 

Case 2] decreasing order , 

At this situation the pivot always fall at last of partition,

Therefore recurrence relation will be ,

T(n) = T(n-1)+T(0)+O(n) ... (Put k=n)

         =O(n^2)