# Question: Let A 1 n be an array of n distinct numbers If i j

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.

a. List the five inversions of the array ¬2, 3, 8, 6, 1¬.

b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ (n lg n) worst-case time. (Hint: Modify merge sort.)

a. List the five inversions of the array ¬2, 3, 8, 6, 1¬.

b. What array with elements from the set {1, 2, . . . , n} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation on n elements in Θ (n lg n) worst-case time. (Hint: Modify merge sort.)

## Answer to relevant Questions

a. Rank the following functions by order of growth; that is, find an arrangement g1, g2, ..., g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), ..., g29 = Ω(g30). Partition your list into equivalence ...A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children. a. How would you represent a d-ary heap in an array? b. What is the height of a d-ary heap of n ...The worst-case number T(n) of comparisons used by SELECT to select the ith order statistic from n numbers was shown to satisfy T(n) = Θ(n), but the constant hidden by the Θ-notation is rather large. When i is small ...Although merge sort runs in Θ (n lg n) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort ...Suppose that instead of always selecting the first activity to finish, we instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy ...Post your question