Selection Sort - Algorithm Analysis

Let us look at the time and space complexity of the Selection Sort algorithm.

As seen in the above diagram, for n element list, there are total n -1 iterations required. Total number of comparisons required in the first iteration is n - 1, in second iteration n - 2, in third iteration n -2 and so on. This is comparison scenario is equivalent to summation series.

Hence, the time complexity of selection sort using asymptotic Big(O) notation is O(n^2). 

If we consider the swap operations, selection sort takes n swaps (1 swap operation in each iteration). According to the asymptotic notation, the value n^2 will dominate for large values of n. Hence this constant value of swap operations can also be dropped for algorithm analysis. So worst case running time for selection sort is O(n^2).

Space complexity for selection sort is O(1). Extra space is required only during swap operation.