Insertion Sort Time Complexity

 We all know the basic formula for the sum of a normal series, and that is: 1 + 2 + 3 +. . . . . . . + n = (n2+n)/2 From the above, it is necessary to use the (n2+n)/2 formula to add the n-th number of series and this way it is take less time.

Another basic thing to say is that time complexity depends largely on the input size and the input variable to be sorted by the for loop or while loop in the program.

Basics became known from the above description. Now let's look at the program of insertion sort again. First of all, we have to pay attention to the for loop or while loop.

for (i=1; i<=n; i++)

    {

        while( )

       {

       }

    }

 

The insertion sort program runs a for loop to take inputs that take in many input arrays.

    for (i=1; i<=n; i++)

    {

        scanf("%d", &array_num[i]);

    }

 

Two loops will run for an n-th number of times n2 and the program will run according to this series 1 + 2 + 3 + . . . . . . . + n because the loop is run 1 to n and it is repeated several times based on the program. The short term we know for this series is: (n2+n)/2

 

Now, the biggest term of the (n2+n)/2 formula is n2. If we consider from two angles, we can see that the time complexity of this insertion sort is n2. Notable, the problem can be described in the form: an2+bn+c which is the representation of Big O notation.

So, the time complexity of Insertion Sort is: O(n2)

Read Similar Posts:

1. BFS Time Complexity

2. Runtime Reduction of a Linear Search

3. Quick Sort Time Complexity

4. Merge Sort Time Complexity

Post a Comment

Previous Post Next Post