Insertion Sort Worst Case
Worst Case
The worst-case happens if the array is sorted in reverse order i.e., in decreasing order. In the reverse order, we always find that A[i] is greater than the key in the while-loop test. Therefore, we must compare each element A[j] along with each element in the entire sorted subarray A[1 .. j − 1] and so tj = j for j = 2, 3, ..., n. Equivalently, we can say that since the while-loop exits because i reaches to 0, there is one additional test after (j − 1) tests. Consequently, tj = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:
And using the summations, we have
This running time can be expressed as (an2 + bn + c) for constants a, b and c that again depends on the statement costs ci. Therefore, T(n) is a quadratic function of n.
Here the punch line is that the worst-case occurs, when line 5 executed j times for each j. This can happens if array A starts out in reverse order
