In our previous post we understood the Loop Invariants and how we can use loop invariants to prove the correctness of our algorithm. We have also covered Insertion Sort algorithm algorithm in the previous posts and now we are going to do an analysis of the Insertion Sort Algorithm.
Analysing Algorithms
There can be multiple algorithms applicable for a given problem and hence it is very important to choose the one which is the most efficient one.
There are mainly 2 ways in which we analyse the algorithm.
- The computational time an algorithm takes to solve a problem.
- The amount of resources consumed by running a particular algorithm. Resources could be memory , communication bandwidth or hardware.
Analysis of Insertion Sort
The running time of an algorithm varies with input. For example sorting a sequence of 1000 integers would take more time as compared to sorting a sequence of 10 integers.
The running time may also vary for the same number of inputs depending on how nearly sorted they already are.
But in general since the running time of an algorithm varies with the size of the input it is defined as the function of the size of its input.
T(n) = f(n)
INSERTION-SORT(A)
In the above procedure we have considered that each line i takes constant constant time ci for execution. Hence line 1 takes a constant time c1 to execute.
Now since line 1 is a loop statement and the control would come to execute that statement until the loop condition is false which means it would be executed n times. Hence the total time taken to execute line 1 throughout the program is c1n.
Line 2 is executed 1 time less than line 1 since it would not be executed when the loop condition is false. So the total time taken to execute line 2 is c2(n – 1).
Line 3 is a comment statement and it would not take any processing time to execute since no operation is performed , although it would be executed n -1 times and the total time taken for execution is 0(n – 1) = 0.
Line 4 would take c4(n – 1)
Line 5 is interesting since we see a summation (∑) over there. Since Line 5 itself is a loop statement and it gets executed multiple number of times for each value of j , lets say when j = 2 the while loop is executed first time when i=1 and the second time when i=0 so hence the execution of line 5 is 2 times for the initial value j=2. We can say that the line 5 is executed tj times. Let us say times taken to execute line 5 one time is c5. The total number of times Line 5 is executed is –
j=2 t2
j=3 t3
j=n tn
This could be represented as 
and the total time taken would be 
Similarly Line 6 and Line 7 would get executed 1 time less than Line 5.
Total time taken by Line 6 = 
Total time taken by Line 7 = 
Total time taken by Line 8 = c8 (n – 1)
Total time taken by the insertion sort algorithm is –
T(n) = c1n + c2 ( n – 1 ) + c4 ( n – 1 ) ++++ c8 (n – 1)
Best Case
The insertion sort algorithm gives the best case when the array is already sorted.
When the array is already sorted the check at Line 5 would fail and Line 5 would be executed just once for each value of j and a total of n – 1 times for the entire program and hence the total time would get changed to c5 (n – 1)
Similarly the time taken by Line 6 and Line 7 would be 0 as the while condition is never satisfied since the elements are already sorted.
The running time of the Insertion Sort for the best case would be –
T(n) = c1n + c2 ( n – 1 ) + c4 ( n – 1 ) + c5 ( n – 1) + c8 (n – 1) = (c1+c2+ c4 + c5 + c8 ) n – (c2+ c4 + c5 + c8 )
This can be expressed as an+b for constants a and b that depend on the statement costs ci , it is thus a linear function of n.
T(n) = n
Worst Case
The worst case of the insertion sort results when the array is in reverse order. In this scenario we will have to compare each of the key element with all the previously sorted element which means the number of times the while loop would be executed is j (tj = 1 ) for j = 2,3,…,n.
Now ,
and
T(n) = (c5/2 + c6/2 + c7/2) n2 + c1 + c2 + c4 + c5/2 - c6/2 - c7/2 + c8 ) n - (c2+ c4 + c5 + c8 )
We can express this as an2+ bn + c for constant a , b and c that again depends upon the statement cost ci it is thus a quadratic function of n.
T(n) = n2
Conclusion
In this post we covered -
- Methods of analysing Algorithms.
- Analysis of Insertion Sort Algorithm
- Understanding the best case performance of Insertion Sort Algorithm
- Understanding the worst case performance of Insertion Sort Algorithm
Book for Reference
Please share the post by clicking the social media icons at the beginning of the post.
Thank you for reading and see you in the next post !👋
Loop Invariants
Insertion Sort Algorithm
What is Algorithm?