The insertion sort method we have described has been shown to have an expected number of comparisons equal to T(n) = , where n is the number of elements to be sorted. That sort method when applied to a fully ordered array runs in \theta(n) time. Now consider a file that is largely ordered in the following sense: noise has been added to each element j in such a way that when the noisy A[i] is to be placed in the array now sorted in the first i-1 elements, the probability that j swaps are needed with the already sorted elements before A[i] is as follows. The probability that a first swap is needed (with A[i-1]) is e ,the probability that a third swap (with A[i-3]) is needed, given that swaps with A[i-1] and A[i-2] were necessary, is and for all preceding elements A[i-j],the probability that a swap with A[i-j]) is needed, given that swaps with A[i-1] through A[i-j+1] were necessary, is .

(i) First, show that the probability that at least j swaps are needed at stage i (for j .

(ii) Assume that the probability of 0 swaps is the complement of the probability that at least 1 swap was necessary; that is, the probability of zero swaps when inserting A[i] is 1e. Then give an expression for the expected number of swaps at stage i in the form of the difference of two sums of similar forms.

(iii) Using the result of part ii, it can be shown that the expected number of swaps at stage i is bounded above by e+ . Sum these upper bounds of expected numbers of swaps from i = 2 to N show that for a file satisfying these conditions the expected value of T(N)= O(N).

(iv) Let C be the expected number of comparisons in this method. Since C(N)= (E[T(N)]), it follows that C(N)= O(N). Then argue that C(N) has to be at least order N (i.e., is in (N)), and as a result T(N)=(N).