Suppose you are given a sequence or array of n real numbers: (a1, a2, . . . , an

Question

Suppose you are given a sequence or array of n real numbers: (a1, a2, . . . , an). We are interested in sorting this list, and ideally sorting it as efficiently as possible / with minimal effort. We can summarize the total ordering information in terms of a permutation of the numbers 1 to n. For instance, given (a1, a2, a3), a total ordering permutation of 3, 1, 2 would tell us that a3 ? a1 ? a2, and therefore that the sorted form of the list would be (a3, a1, a2).

6) Argue that for >=1, n!<=nn.

7) Argue that for n >= 2, n! >=(n/2)^(n/2).

8) What can you conclude about the asymptotic growth / order of ln(n!)? What can you conclude about the minimal number of tests/comparisons needed to sort a list?

9) Argue that merge sort has a complexity of ?(n ln n) and therefore is, asymptotically, as or more efficient than any other sorting algorithm.

Bonus) What are the tightest (simple) bounds you can achieve and verify on ln(n!)?

Explanation / Answer

suppose you are given an array of n elements of which a[0] is the first element and a[n] is the last element. To sort the array of elements, there are so many algorithms available but if you bring the concept of total ordering of elements, then the problem cuts down to selection of one ordering.

1) How many possible total ordering permutations are there?

A) if you have n distinct real numbers in your array, then the number of total ordering permutations available are n! which is nothing but the total number of permutations of the n elements.

2) Argue that if you know or are given the total ordering permutation, then you can sort the list without any additional comparisons or tests.

A) IF you are given total ordering permutation, then the procedure is to select that order where the elements of the array are ordered. in this case you do not have to compare the elements of the array or you dont even have to use a sorting algorithm.

3) Argue that if you don’t know the total ordering permutation (or only know partial / incomplete information about it), you cannot sort the list without additional comparisons or tests.

A) If you dont know the total ordering permutation, then the elements of the array may have partially/not sorted and compulsorily we have to intercompare the elements of the array to get the sorting order.

5) If every element comparison (testing whether ai ? aj ) provides one bit of information, argue you need at least on the order of ln(n!) many tests/comparisons to sort the list.

A) This part is tricky. if you compare two elements, then you have a little bit of information and you can easily arrange other elements with respect to these two elements. Consider the case of binary sort/heap sort, all the elements in the tree will be in order and the new elements will be placed in their corresponding place. The time complexity of the sorting techniques are of order nlogn. If you use linear sorting algorithms, then in the worse case you do have time complexity of order n2 (in case of bubble sort)
================pc and sc

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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