Question

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.

1.

Which arrays with distinct elements from the set {1, 2, . . . , n} have the smallest

and the largest number of inversions and why? State the expressions exactly in terms of n.

2.

For any 0 < a < 1/2, construct an array for which insertion sort has a run time of an^2 + Θ(n).

3.

Let A[1, . . . , n] be a random permutation of {1, 2, . . . , n}. What is the expected

number of inversions of A. What can you conclude about the average case running time of

Insertion-Sort (where the average is over all arrays A of size n)?

Hint: Recall the linearity of expectation, i.e., for any real a, b, c and any random variables

X, Y , E(aX + bY + c) = aE(X) + bE(Y ) + c .

Answer 1

Answer 1

Smallest inversions array are arrays with values in ascending order from 1 to n.

Smallest Inversions Array Example = [1, 2, 3, 4, 5, 6, 7, 8, 9]

Number of Inversions = 0

Largest inversions array are array with reverse order of element.

Largest Inversions Array Example = [9, 8, 6, 5, 3]

Number of inversions = (n-1) + (n-2) +...+1 = n(n-1)/2

Answer 3

Let's consider X_ij represents the indicator random variable for the event that A_i > A_j (i<j).

Probability of two distinct integers having inversion is half so expected number

Assuming X is the random variable which denotes the total number of Inverted pairs then