OBLEM 4: analysis (50 points): ceis a \"Divide-And conquer\" sorting Algorithm W

Question

OBLEM 4: analysis (50 points): ceis a "Divide-And conquer" sorting Algorithm We will call Here SILLY SORT If ns2, sort the elements by making at most one comparison and a (possible) swap. Otherwise: (1) Recursively silly_sort the last two thirds of the array (rounding up). (Ceiling of 2n/3elements). (2) Recursively silly sort the first two thirds of the array (again rounding up) (3) Recursively silly sort the last two thirds of the array (again rounding up). Your job: you have two tasks: I. (20 points) Argue the correctness of the algorithm. (Think about what must be true after step 1; then what must be true after step 2). Your argument does not need to be a formal proof, but it should be "inductive" II. Analysis: A. (15 points) Write a recurrence relation expressing the runtime of SILLY SORT Your recurrence relation will be of the form "T(N) B. (10 points) Do some research on the internet on the "Master Theorem." Apply the Master Theorem to your answer to (A) to derive a tight runtime bound for SILLY-SORT (i.e., a . bound) slower, faster or equivalent to that of Selection Sort? Explain. c. (5 points) Is the runtime of SILLY_SORT asymptotically

Explanation / Answer

I. For a list L, let P(L) be the statement that Sillly_Sort(L) correctly sorts L into nondecreasing order. We will prove P(L) is true for any list L by strong induction on |L|.

As a base case, consider when |L| = 1. This one-element list is already sorted, and our algorithm correctly returns L as the sorted list.

For the induction hypothesis, suppose that P(L) is true for all lists of length < n; that is, suppose that for any list L of length < n, Silly_Sort(L) correctly sorts L. Now consider a list L of length n. The algorithm divides L into three parts last two third A, first two third B and last two third C. Each of length < n; therefore, A*, B* and C* are in sorted order by our induction hypothesis.

The minimum element of L is therefore either the minimum element of A* (which is at the front of A* ) or the minimum element of B* (which is at the front of B* ). And the maximum element of L is either the maximum of B* or the maximum of C*.

Therefore we have shown by induction that Silly_Sort(L) correctly sorts any list L.

II) A) Since Silly_Sort divides the whole list into three parts and sort each part the recurrence relation will be of the form:

T(N) = 3 *T(2n/3) + O(1)

II) B) Master Theorem:

Master Method is a direct way to get the solution. The master method works only for the following type of recurrences or for recurrences that can be transformed into the following type.

There are following three cases:
1. If f(n) = (nc) where c < Logba then T(n) = (nLogba)

2. If f(n) = (nc) where c = Logba then T(n) = (ncLog n)

3.If f(n) = (nc) where c > Logba then T(n) = (f(n))

For Silly_Sort algorithm recurrence time complexity is of:

T(N) = 3 *T(2n/3) + O(1)

It fits the case 1, which gives:

O(nlog3/23) = O(n2.71)

So, time complexity of Silly_Sort is O(n2.71)

II) C) Time complexity of Silly_Sort is O(n2.71) while of selection sort is O(n2). It clearly shows that Silly_Sort is even slower than selection sort.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

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