Time Complexity Analysis

What is Time Complexity?

Time complexity is an analysis of the time it takes for an algorithm to run in comparison to the size of the input. It is used to see how efficient a computer algorithm is and is measured as a polynomial or exponential function in the worst, best, and average cases.

Time complexity of Selection Sort

The number of iterations that selection sort will require based on the number of elements in the array (N) is O(N^2) in the worst case since there are N elements and at each iteration of the index j, N - j iterations are needed to find the minimum element for a total of N * (N + 1) / 2 iterations or O(N^2) time. The best case running time is Ω(N^2) time, the same as the worst case.

Time complexity of Insertion Sort

The number of iterations that insertion sort will require based on the number of elements in the array (N) is O(N^2) in the worst case since if the array is pre-sorted in decreasing order, insertion sort will make N iterations for each of the N elements for a total of O(N^2). However, the best case of insertion sort is Ω(N) time since if the array is pre-sorted in ascending order, no swapping is needed and the algorithm will simply iterate through the N elements for a total of Ω(N).