# Question: Let A 1 n be an array of n distinct

Let A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Use indicator random variables to compute the expected number of inversions.

**View Solution:**## Answer to relevant Questions

Professor Marceau objects to the loop invariant used in the proof of Lemma 5.5. He questions whether it is true prior to the first iteration. His reasoning is that one could just as easily declare that an empty subarray ...What are the minimum and maximum numbers of elements in a heap of height h?Suppose that the splits at every level of quick sort are in the proportion 1 - α to α, where 0 < α ≤ 1/2 is a constant. Show that the minimum depth of a leaf in the recursion tree is approximately - lg ...Show how to sort n integers in the range 0 to n2 - 1 in O (n) time.Suppose we use a hash function h to hash n distinct keys into an array T of length m, assuming simple uniform hashing, what is the expected number of collisions? More precisely, what is the expected cardinality of {{k, l} : ...Post your question