Question

When asked to describe an algorithm you are expected to give a clear pseudo-code description of the algorithm

1. (10 pts) Here is a new sorting algorithm NewSort Suppose the original call made is NewSort(A,0,n-1) where A is an array integers. == void NewSort(int A[], int i, int j){ \\ sorts the subarray Aſi..j] if (j i+1) \\when there are only 2 elements if (A[i] > A[j]) swap(A,i,j) \\swaps A[i] and A[j] else { int k = (j-i+1)/3; NewSort(A,i,j-k); \\ sort first two thirds NewSort(A, i+k, j); \\ sort second two thirds NewSort(A,i,j-k); \\ sort first two thirds again } } (a) Let T(n) denote the time complexity for NewSort to sort an array of n elements. The general recurrence relation expressing the run time of this algorithm is T(n) = 3T (2n/3) +0 (b) Between MergeSort, Randomized-Quicksort, and NewSort, which would you recom- mend? When and why? Explain

Answer 1

ca As we have T(n) to soot an time complexity for Newsort array of n elements Given algorithm recurrence relation T(n) = 3T (20/3) + c ) -0 of sun time Jor this こ Let & solue this recurrence Master & theorem. Jelarien using Extended According to Extended Master & Theorem. T(n) at(nb) + o (nklogen) where Applying this relation on O have, and as c is constant is may be written as bol k zo and p is realno, we a=3 b= 3/2 - (nologn) b=3/2 ,k=o q=3 and p=0 Now, L a>bk then 7(n) = 0 (n logo) (a =3) > T(n) = 0 (n logas ñ 6k

Z log312 T(n) = 0 (n logo/ ) 2.70 our algorithm 2 Tn) 0(m2) time complexity Hence. Time complementy of og Newsost. As we know that time complexity Menge sort - Olnegn) #me completing of Randomizel. - Cuickport - Olnego) our Algorithin Newsort Ince, According to o orymptotice ordering of function ne grows faster than lign. O(n) will takes more time then O(nlan) I will recommend for randomized-Cuicksort noen are distinct ano pivot elements . It will be fastest - Inlgn) I will recommend merge-sort when there is a large file to sort and smaller RAM We can perform external morge-sort an Our algorithm Newsort Now sort its not recommended because taking time which is extremely slow and "Can not work properly with computer. elements there are selected randomly e we have available. faster way. * O ) 0 (287) it uls