Question

What is the role of pivot in quick sort? Will the efficiency of the algorithm in best case change based on the selection of pivot or otherwise?

Answer 1

Role of pivot in Quick Sort: A pivot divides the list or array into two parts. For each partition, we find the pivot recursively and subdivide the list/array further.

The time taken by quick sort algorithm is written as:
T(n) = T(k) + T(n-k-1) + (n) , where the list is partitioned around the pivot at K th position
T(k) is the time taken for recursive calls from 0th index to Kth index.
T(n-k-1) is the time taken for recursive calls from (K+1) to last index.
(n) is for partition process.

The best case occurs when the partition process always picks the middle element as pivot.
Equation becomes: T(n) = 2T(n/2) + ​​​​​​​(n)
Here the pivot is at (n/2) th index.
The solution of above recurrence is ​​​​​​​(n Log n) by Master's Theorem.

If the pivot is changed to say, the first index or the last index,
Equation becomes: T(n) = 2T(n/2) + ​​​​​​​(n)
The solution of recurrence relation is ​​​​​​​(n² ) , which is the worse case scenario.

If the pivot is taken as any other index, then time complexity becomes O(n Log n) which is the average case.