Average case The"average case"is often roughly as bad as the worst case.Suppose that we randomly choose n numbers and apply insertion sort.How long does it take to determine where in subarray A[1..j-1]to insert element A[j]?On average, half the elements in A[1..j-1]are less than A[j],and half the elements are greater.On average,therefore,we check half of the subarray A[1..j-1],and so t;is about j/2.The resulting average-case running time turns out to be a quadratic function of the input size,just like the worst-case running time.Average case