Time and Space Complexity

FOR TIME COMPLEXITY

For every cycle number of comparisons are as follows i.e. for 1st cycle comparisons are (n-1), for 2nd cycle comparisons are (n-2), and so on...

For Last Cycle Comparisons will be one.

So Total Number of Comparisons are: (n-1)+(n-2)+...+1 = n(n-1)/2 which is roughly equal to n^2

So the complexity of Selection Sort will be O(n^2).

• Best Case Complexity - It happens when the array is already sorted i.e. no sorting is required. The time complexity of selection sort in this case is O(n^2).
• Average Case Complexity - It happens when the array elements are in jumbled order i.e. not properly ascending or descending. The Average Case time complexity of selection sort is O(n^2).
• Worst Case Complexity - It happens when the elements of an array are required to be sorted in reverse order. This means if we have elements in ascending order and we have to sort them in descending order or vice-versa. The time complexity of selection sort in case is O(n^2).

 

FOR SPACE COMPLEXITY

• The space complexity of selection sort is O(1). It is because, an extra variable is required for swapping in selection sort.