Question

PLEASE READ CAREFULLY AND ALL THE WAY THROUGH!!! I already asked this question but unfortunately the person who answered it did not read it.

There is a sorting algorithm, “Stooge-Sort” which is named after the comedy team, "The Three Stooges." if the input size, n, is 1or 2, then the algorithm sorts the input immediately. Otherwise, it recursively sorts the first 2n/3 elements, then the last 2n/3 elements, and then the first 2n/ 3 elements again. The details are shown in Algorithm below.

            Algorithm StoogeSort(A, i, j ):

            Input: An array, A, and two indices, i and j, such that 1 £ i £ j < n

            Output: Subarray, A[i..j] ,sorted in nondecreasing order

            1.         n ¬ j – i + 1    // The size of the subarray we are sorting

            2.         if n = 2 then

            3.             if A[i] > A[j] then Swap A[i] and A[j]

            4.             else if n > 2 then

            5.                     m ¬ ën/3û

            6.                     StoogeSort(A, i, j-m)   // Sort the 1^st part.

            7.                     StoogeSort(A, i+m, j) // Sort the last part.

            8.                     StoogeSort(A, i, j-m)   // Sort the 1^st part again.

            9.         return A

1) Suppose we change the assignment statement for m (on line 5) to the following:

            m ¬ max {1, ë n/4 û

A) Characterize the running time, T(n), in this case, using a recurrence equation.

B) Using the Master’s Theorem, decide the asymptotic bound for T(n) in (A).

Answer 1

In each recursive call, the problem is dividing into three sub problems of size 2n/3. Thus, the recurrence relation that represent the running time of the algorithm will be as follows: T(n)-3T(2n/3)+0(1)-O(no3Hog(3/2) or O(n27) a) Now change the assignment m-max {Ln / 41 That is we are splitting the array A into four sub arrays. Thus the StoogeSort sorts first three- fourth of A of size n-m first, then it sorts the last three-fourth of A of size n-m. Finally, it agairn sorts the first three-fourth of A of size n-nm Thus the new recurrence equation that represents the running time of StoogeSort is as follows: T(n)-3T(3n/4)+0(1) b) Consider the recurrence relation T(n)-37(3n/4)+0(1) or T(n)-3T(3n/4)+O(n0) We can solve the above recurrence using master theorem log8 By case 1 of master theorem(a-3b-4/3 and e 2), T(n) EO n 7(n)-e(n3 81) Since, log-log43#3.81,

Also we can prove that the StoogeSort works correctly using inducntion as follows: Consider the given Stooge Sort algorithm Base case(n-I or n-2): * Ifn-1, all the lines are skipped, and the input array is returned as it is, in the line 9(last ine * If n-2, line 2 and 3 guarantee that the first element is less than the second element and returns the sorted arrav, Thus, the StoogeSort works correctly for n-1 and n-2. Inductive hypothesis(n F3): Assume StoogeSort sorts correctly, any array of size < n. Now, it is enough to show that the StoogeSort works correctly for any array of length n. Induction: Consider an array A of size n. * Splits the array into three sub arrays of each sizes m,n-2m and m respectively. where m-|n/3 |. In the line 6, StoogeSort is called recursively on the subarray(first two- thirds of array A of size n-m)

We assume n2 3. Thus m21. That is n-m is strictly less than n. Thus, we can apply inductive hypothesis on this sub array of length r-m. That is, StoogeSort sorts correctly the array of length n-m * After line 6, largest m elements of the sub array will be in the second third of A. . In line 7, StoogeSort is called recursively on the subarray(last two-thirds of array A of size n-m). It is known that, n-mn. By induction hypothesis, this sub array is sorted correctly by StoogeSort. . Remember that, After line 6, all the m largest elements of two-thirds of A are moved to middle or second third of A. Now, after line 7, all the m largest elements of A are moved to last third of A in sorted order. As a result few elements are less than some elements in the first third of A. . In line 8, StoogeSort sorts first two-thirds of A of size n-m. Since n-m<n, by inductive hypothesis, this sub array is correctly sorted by StoogeSort . That is, after line 8, few elements that are less than some elements in the first third are moved to first third of A and the sub array will be in sorted order Thus, final array A is in sorted order. Therefore, by induction, it is proved that StoogeSort sorts works correctly.