Algoeithm Design, Analysis and Implementation Assignment

Algoeithm Design, Analysis and Implementation - Assignment Example This is done by choosing a comparison element and placing all the elements that are less than the comparison element in the first group and the rest of the elements in the second group. This procedure is repeated recursively until the elements are sorted (a part consist of only one element). T(n) = (n-1) + ?1 ? i ? n ti As 1,2,....k-elements are already sorted, we can say that ti =0, where i = 1,2, 3... k. Then, the contribution of quick sort when early stopping is used can be given by, T(n)=(n+1)( ?k ? i ? n ti + ?(1)) = (n+1)( n lg +?(1)) =2n lg +?(n) Thus, T(n) for quick sort =O(nlg(n/k)). Given that, insertion sort is done on a partially sorted array (unsorted k-elements). In general, running time of insertion sort is O(n2 ), where n is the length of the array (total number of elements). In order to provide a solution to this problem, the total array is divided into subarrays of k-elements each, such that k/2? n ? k, then n = O(k) and the running time of insertion sort is O(k2). The total number of such subarrays (m) would then be n/k ? m ? 2n/k., which implies m = O(n/k). The total time spent on insertion sort would then be O(k2)* O(n/k) = O(nk). T(n) for insertion sort = O(nk). Therefore, the total time for this sorting algorithm is as follows: T(n) = O(nk + nlg(n/k) ). ... Solution: From the above problem (1), we find that quick sort sorts k-elements of an n-element array O(n log(n/k)) time. Quick sort sorts by partitioning the given array A[p...r] into two sub-arrays A[p...q] and A[q+1... r] such that every element in A[p...q] is less than, or equal to, elements in A[q+1... r]. This process is repeated until all the elements are sorted. Algorithm for quick sort is given by: A[P] is the pivot key upon which the comparison is made. P is chosen as the median value of the array at each step. If the element is less than, or equal to, the pivot key value, it is moved left. Otherwise, it is moved right. Assuming the best case scenario where each step produces two equal partitions, then T(n)=T(n/2)+T(n/2)+?(n) =2T(n/2)+ ?(n) By Master’s Theorem case 2, T(n) = O(n lg n) In other words, the depth of recursion is log n and at each level/step, the number of elements to be treated is n. If only k-elements are sorted, then the depth of recursion would be n/k and the number of elements would be n at each level, the time taken by this sorting algorithm is given by T(n) = O(n lg (n/k)). 2.2 Show that we can sort a k-well-sorted array of length n in O(n log k) time. As the array is already sorted for k-elements, the remaining steps required to complete the sort would be k (using the results from 1), then T(n) = O(n lg k). 3. Computing the k-th smallest element in the union of the two lists m and n using O(lg m +lg n) time algorithm: Approach 1: Merge sort can be used in this case. It splits the list into two halves, recursively sorts each half, and then merges the two sorted sub-lists. In the given problem, the lists are already sorted; hence, the