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:
2. Runtime Reduction of a Linear Search