In this article, you will learn about Time Complexity and Space Complexity of Selection Sort algorithm along with the complete mathematical analysis of the different cases. You must go through this guide in detail.

In short:

• Worst Case Time Complexity is: O(N²)
• Average Case Time Complexity is: O(N²)
• Best Case Time Complexity is: O(N²)
• Space Complexity: O(1)

The number of swaps in Selection Sort are as follows:

• Worst case: O(N)
• Average Case: O(N)
• Best Case: O(1)

We have covered the following:

• Overview of Selection Sort Algorithm
• Analysis of Worst Case Time Complexity of Selection Sort
• Analysis of Average Case Time Complexity of Selection Sort
• Analysis of Best Case Time Complexity of Selection Sort
• Analysis of Space Complexity of Selection Sort
• Conclusion

Overview of Selection Sort Algorithm

The basic idea of Selection Sort is find the smallest element in the unsorted array and add it to the front of the array. In Selection Sort, we maintain two parts:

• Sorted sub-array
• Unsorted sub-array

In sorted sub-array, all elements are in sorted order and are less than all elements of the unsorted sub-array.

The pseudocode of Selection Sort is as follows:

// Selection Sort
array = [a1, a2, ..., aN]

for i from 0 to N-1
    for j from i to N-1
        int smallest_index = smallest(array[j ... N-1])
        if (smallest_index != i)
            swap(i, smallest_index)
        
// Find the smallest element
smallest(int array):
    smallest_index = 0
    smallest = array[0]
    for index from 1 to M
        if smallest > array[index]
            smallest = array[index]
            smallest_index = index
            
    return smallest_index

With this, you have the basic idea of selection sort.

Time Complexity Analysis of Selection Sort

At the beginning, the size of sorted sub-array (say S1) is 0 and the size of unsorted sub-array (say S2) is N.

At each step, the size of sorted sub-array increases by 1 and size of unsorted sub-array decreases by 1. Hence, for a few steps are as follows:

• Step 1: S1: 0, S2: N
• Step 2: S1: 1, S2: N-1
• Step 3: S1: 2, S2: N-2
  and so on till S1 = N. Hence, there will be N+1 steps.

Hence, S2 = N - S1

The Time Complexity of finding the smallest element in a list of M elements is O(M). This is constant for all worst case, average case and best case.

The time required for finding the smallest element is the size of unsorted sub-array that is O(S2). The exact value of S2 is dependent of the step.

For step I, S1 will be I-1 and S2 will be N-S1 = N-I+1.
So, the time complexity for step I will be:

• O(N-I+1) for find the smallest element
• O(1) for swapping the smallest element to the front of unsorted sub-array

I will range from 1 to N+1.

Hence, the sum of time complexity of all operations will be as follows:

Sum [ O(N-I+1) + O(1) ] for I from 1 to N+1
= Sum [O(N-I+1)] + Sum[O(1)] ... Equation 1

Sum [ O(1) ] = 1 + 1 + ... + 1 [(N+1) times] = N+1 = O(N)

Sum [O(N-I+1)] = N + (N-1) + ... + 1 + 0 =
= 1 + 2 + ... + N
= N * (N+1) / 2
= (N^2 + N) / 2 = O(N^2) + O(N) = O(N^2) [as N^2 is dominant term]

Therefore, from Equation 1, we get:
Sum [O(N-I+1)] + Sum[O(1)]
= O(N^2) + O(N)
= O(N^2)

Hence, the time complexity of Selection Sort is O(N²).

Worst Case Time Complexity of Selection Sort

The worst case is the case when the array is already sorted (with one swap) but the smallest element is the last element. For example, if the sorted number as a1, a2, ..., aN, then:

a2, a3, ..., aN, a1 will be the worst case for our particular implementation of Selection Sort.

Worst Case: a2, a3, ..., aN, a1

The cost in this case is that at each step, a swap is done. This is because the smallest element will always be the last element and the swapped element which is kept at the end will be the second smallest element that is the smallest element of the new unsorted sub-array. Hence, the worst case has:

• N * (N+1) / 2 comparisons
• N swaps

Hence, the time complexity is O(N^2).

Best Case Time Complexity of Selection Sort

The best case is the case when the array is already sorted. For example, if the sorted number as a1, a2, ..., aN, then:

a1, a2, a3, ..., aN will be the best case for our particular implementation of Selection Sort.

This is the best case as we can avoid the swap at each step but the time spend to find the smallest element is still O(N). Hence, the best case has:

• N * (N+1) / 2 comparisons
• 0 swaps

Note only the number of swaps has changed. Hence, the time complexity is O(N^2).

Average Case Time Complexity of Selection Sort

Based on the worst case and best case, we know that the number of comparisons will be the same for every case and hence, for average case as well, the number of comparisons will be constant.

Number of comparisons = N * (N+1) / 2

Therefore, the time complexity will be O(N^2).

To find the number of swaps,

• There are N! different combination of N elements
• Only for one combination (sorted order) there is 0 swaps.
• In the worst case, a combination will have N swaps. There are several such combinations.
• Number of ways to select 2 elements to swap = nC2 = N * (N-1) / 2
• From sorted array, this will result in O(N^2) combinations which need 1 swap.

So,
0 swap = 1 combination
1 swap = O(N^2) combinations
2 swap = O(N^4) combinations
...
N swaps = O(N) combinations

Hence, the total number of swaps will be:

0 + O(N^2) + 2 * O(N^4) + ... + N * O(N)
= O((N+1)!)

Hence, the average number of swaps will be N that is O((N+1)!) / O(N!). Hence, the average case has:

• N * (N+1) / 2 comparisons
• N swaps

Space Complexity of Selection Sort

The space complexity of Selection Sort is O(1).

This is because we use only constant extra space such as:

• 2 variables to enable swapping of elements.
• One variable to keep track of smallest element in unsorted array.

Hence, in terms of Space Complexity, Selection Sort is optimal as the memory requirements remain same for every input.

Conclusion

With this article at OpenGenus, you must have the complete idea of Time and Space Complexity of Selection Sort. As a summary,

• Worst Case Time Complexity is: O(N²)
• Average Case Time Complexity is: O(N²)
• Best Case Time Complexity is: O(N²)
• Space Complexity: O(1)

The number of swaps in Selection Sort are as follows:

• Worst case: O(N)
• Average Case: O(N)
• Best Case: O(1)