Perform an “average case” time complexity analysis for Insertion-Sort, using the given proposition
and definition. I have broken this task into parts, to make it easier.
Definition 1. Given an array A of length n, we define an inversion of A to be an ordered pair (i, j) such
that 1 ≤ i < j ≤ n but A[i] > A[j].
Example: The array [3, 1, 2, 5, 4] has three inversions, (1, 2), (1, 3), and (4, 5). Note that we refer to an
inversion by its indices, not by its values!
Proposition 2. Insertion-Sort runs in O(n + X) time, where X is the number of inversions.
(a) Explain why Proposition 2 is true by referring to the pseudocode given in the lecture/textbook.
(b) Show that E[X] = 1
4n(n − 1). Hint: for each pair (i, j) with 1 ≤ i < j ≤ n, define a random indicator
variable that is equal to 1 if (i, j) is an inversion, and 0 otherwise.
(c) Use Proposition 2 and (b) to determine how long Insertion-Sort takes in the average case.
