3. (25 points) Let A[1..] be an array of n distinct numbers. If i A, the pair (i

Question

3. (25 points) Let A[1..] be an array of n distinct numbers. If i A, the pair (i,j) is called an inversion of A. (a) List all the inversions of the array(2,3, 8,6, l). 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 (see question 2) and the ns in the input array? Justify your answer. (d) Suppose we are comparing implementations of insertion sort and merge sort (a more advanced sorting algorithm, which we will learn about later in the semester) on the same machine. For inputs of size n, insertion sort runs in 8n2 steps, while merge sort runs in 64n log2n steps. For which values of n does insertion sort beat merge sort?

Explanation / Answer

Hi,
Inversions are defined as when i<j then a[i]>a[j]
given array is a={2,3,8,6,1}
therefore inversions are

8n2 < 64nlogn

=n < 8logn

=n/8 < logn

i.e n-8logn>0

on solving the equality we get, n=43
therefore for n<=43, insertion sort is better

Thumbs up if this was helpful, otherwise let me know in comments. Good Day.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.