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.

a. Proposition 2 states that Insertion-Sort runs in O(n + X) time, where X is the number of inversions.

b. The expected number of inversions, E[X],  E[X] = 1/4n(n-1).

c. In the average case, Insertion-Sort has a time complexity of approximately O(1/4n²).

(a) Proposition 2 states that Insertion-Sort runs in O(n + X) time, where X is the number of inversions. To understand why this is true, let's refer to the pseudocode for Insertion-Sort:

InsertionSort(A):

  for i from 1 to length[A] do

     key = A[i]

     j = i - 1

     while j >= 0 and A[j] > key do

        A[j + 1] = A[j]

        j = j - 1

     A[j + 1] = key

b. The expected number of inversions, E[X], can be calculated as follows:

E[X] = Σ(i,j) E[I(i, j)]

= Σ(i,j) Pr((i, j) is an inversion)

= Σ(i,j) 1/2

= (n(n-1)/2) * 1/2

= n(n-1)/4

Hence, E[X] = 1/4n(n-1).

(c) Using Proposition 2 and the result from part (b), we can determine the average case time complexity of Insertion-Sort. The average case time complexity is given by O(n + E[X]).

Substituting the value of E[X] from part (b):

Average case time complexity = O(n + 1/4n(n-1))

Simplifying further:

Average case time complexity = O(n + 1/4n^2 - 1/4n)

Since 1/4n² dominates the other term, we can approximate the average case time complexity as:

Average case time complexity ≈ O(1/4n²)

Therefore, in the average case, Insertion-Sort has a time complexity of approximately O(1/4n²).

Learn more about proposition on

https://brainly.com/question/30389551