Insertion Sort - Time Complexity

 Time Complexity of Insertion Sort

Selection Sort is using two for loops to do one iteration. The first loop (Outer loop ) travels through an array starting from index 0, while the inner loop runs from index i+1 to index less than i. The following diagram shows the Number of execution rounds it performs.

when i is 0,, j is 1,  the inner for loop runs n-1 time. when i is 1, j is 2, the inner for loop runs n-2 times. Likewise, when i is n, j is n+1,  the inner for loop runs n times.

So the total number of Execution rounds can be calculated by adding all Execution times in each i values. 

Time Complexity =    n-1 (n-1)

                                             2

                                =   n² - n - 1

                                      2          2

since the determinant factor is square of n, time complexity depends on only the square of n.

 

                       F(n) = O (n²)