BEST CASE TIME COMPLEXITY

The best case time complexity for Selection sort would be the given array or linked list to be sorted is already in ascending order i.e it is already sorted.

Consider the given array :

The selection sort algorithm has a best-case time complexity of O(n) for the already sorted array because here, only the outer loop is running n times, and the inner loop is kept still.

WORST CASE TIME COMPLEXITY

The worst case time complexity for Selection sort would be the given array or linked list to be sorted is already in descending order.

Consider the given array :

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 Selection sort would be the given array or linked list is unsorted.

Consider the given array :

Here the recurrence relation would be (n-1) & the Time complexity for average case would be derived same as worst case time complexity.
The Average case time complexity for Selection Sort would be :

T(n)=n²