Insertion Sort Best Case Homework Help
The best case happens if the array is already sorted. For each j = 2, 3, ..., n, we find that A[i] less than or equal to the key when i has its initial value of (j − 1). In other words, when i = j −1, always find the key A[i] upon the first time the WHILE loop is run.
Consequently, tj = 1 for j = 2, 3, ..., n and also the best-case running time could be calculated utilizing equation (1) as follows:
This running time can be expressed as an + b for constants a and b that depend on the statement costs ci. Therefore, T(n) it is a linear function of n.
The punch line here is that the while-loop in line 5 executed only once for each j. This happens if given array A is already sorted.
It is a linear function of n.
