Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search
Tuesday, February 23, 2010
Let A[1 .. n] be an array of n distinct numbers. If i <> A[j], then the pair (i, j) is called an inversion of A. Suppose that each element of A is chosen randomly, independently, and uniformly from the range 1 through n. Compute the expected number of inversions.