BEST CASE TIME COMPLEXITY

The best case time complexity for Qucik sort would be that the pivot element is present at the middle position of the array.

Consider the given array :

Here let us consider 15 as the pivot element as it is present at the (n+1)^thindex of the array.

In the best-case scenario for QuickSort, the recurrence relation can be defined as follows:
T(n) = 2T(n/2) + O(n)

Here, T(n) represents the time complexity of sorting an array of size 'n' in the best-case scenario. The recurrence relation states that the time complexity of QuickSort in the best-case scenario is equal to twice the time complexity of sorting each half of the array (n/2) plus the time complexity of the partitioning step (O(n)).

The factor of 2 in the recurrence relation arises because, in the best case, the chosen pivot consistently divides the array into two roughly equal-sized subarrays.

T(n) = 2*T(n/2) + n ..............(1)
Here the dividing factor is n/2 so substitute the value of n as n/2.
T(n/2) = 2*T(n/4) + n/2 ..............(2)
T(n/4) = 2*T(n/8) + n/4 ..............(3)

Now we have to perform backsubstitution to get the value of T(n).
T(n) = 2*T(n/2) + n .............from eq(1)
T(n) = 2*[2*T(n/4)+ n/2] + n
T(n) = 4*T(n/4) + 2n ..............(4)
T(n) = 4*[2*T(n/8)+n/4] + n
T(n) = 8*T(n/8) + 3n ..............(5)

from above eq(4),(5) we can conclude that :
T(n) = 2^k * T(n/2^k) + kn .............(A)

Here we consider n/2^k as 1 so that we can efficiently find the time complexities.
n/2^k = 1
n = 2^k
taking log on both sides.
log n = log(2^k)
i.e. logn =klog2
logn = k
eq.(A) becomes :
T(n) = n*T(1) + nlogn
i.e. T(n) = n + nlogn
T(n) = nlogn ............considering only dominant terms

WORST CASE TIME COMPLEXITY

The worst case time complexity for quick sort would be that the pivot elemt is present at zero^th index or (n-1)^th index.

Consider the given array :

The recurrence relation for the worst-case time complexity of QuickSort can be defined as follows:

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

Here, T(n) represents the time complexity of sorting an array of size 'n' in the worst-case scenario. The recurrence relation states that the time complexity of QuickSort in the worst case is equal to the time complexity of sorting an array of size (n-1) plus the time complexity of the partitioning step (O(n)).
Here , the recurrence relation would be :
T(n) = T(n-1) + n ............(1)

So the dividing factor would be (n-1).
Substitute the value of n as (n-1) in eq.(1)
T(n-1) = T(n-2) + (n-1) ..........(2)
Again rebsubstite the values :
T(n-2) = T(n-3) + (n-2) ..........(3)
T(n-3) = T(n-4) + (n-3) ..........(4)

Now Backsubstituting the values :
Consider eq(1) :
T(n) = T(n-1) + n
T(n) = T(n-2) + (n-1) + n ...................from eq.(2)
T(n) = T(n-3) + (n-2) + (n-1) + n ...........from eq.(3)
T(n) = T(n-4) + (n-3) + (n-2) + (n-1) + n....from eq.(4)

So the above equation can be written as : T(n) = T(n-k) + ⁿ⁽ⁿ⁺¹⁾ ⁄ ₂
We need to eliminate T(n-k). So we put n-k=1 so n=k+1
hence the above equation becomes :
T(n)=T(1) + ^(k+1)(k+2) ⁄ ₂
So it becomes T(n) = k²+3k+2 ;
We only consider dominant terms so T(n)=k² i.e

T(n)=n²

AVERAGE CASE TIME COMPLEXITY

The average case time complexity for quick sort will be the pivot selection process is assumed to divide the array into two roughly equal-sized subarrays with high probability.

Consider the given array :

Here the recurrence relation would be same as best case and would be derived in the same process.
The Average case time complexity for Quick Sort would be :

T(n)=n²