Best Case Time ≅ K*Nfor someK(Notice that there is no exponent on the N.)
If the array is already sorted, then the inner loop does nothing.
The only thing that happens is the outer loop executes N times.
Best case performance is pretty good. Of course, if the array is already sorted, there is no reason to sort it again.
for (int j = 1; j < N; j++)
{
loop: insert list[j] into its proper place in sub-list of size j
}
What about worst case performance?
This is when the list to be sorted is in descending order.
Then for each iteration of the outer loop,
the inner loop executes j times,
and the total number of iterations is:
1 + 2 + 3 + 4 + ... + (N-2) + (N-1) = (N*(N-1))/2
This is half as fast as average case, but still proportional to N2.
If you knew that a list was in backwards order would you need to sort it?