verage 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 y A1. j-1 to insert element Ali On average half the elements in A[l .j-l are less than A[jl, and half the elements are greater. On average, therefore, we check half of the subarray A[l.j-l, 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 timeAverage case