Question

For [Select], there are three choices: worse than, the same as, better than

Answer the following questions about the computational properties of divide-and-conquer sorting algorithms, based on tight big-Oh characterizations of the asymptotic growth rate of the functions for the running time or space size, depending on the question. Assume that the input sequence is given as a list, and the output sequence is also a list. Also assume a general implementation of the sorting algorithms, as opposed to an in-place implementation; that is, during any individual call, the divide-and-conquer algorithm creates new lists to pass the corresponding sub-lists of the input sequence during the "divide" part of the algorithm, before the "recursive" part (i.e., the constructed input for each sub-problem are recursively passed-by-value using lists), and returns the output as using a list data structure. The "conquer" part of the algorithm then operates on the output list returned from the "recursive" part. Assume that insertions to and deletions from both the front or the back of a list, as well as concatenating two lists, take worst-case constant time and space, while traversing the list takes worst-case linear time and constant space. 1. In terms of worst-case running time, the "divide" part (i.e., before the recursion) of quick-sort is [Select] that of merge-sort. 2. In terms of worst-case running time, the "conquer" part i.e., after the recursion) of quick-sort is [Select] that of merge-sort. that of merge-sort. 4. The expected running time of quick-sort is [Select] that of merge-sort. 5. In terms of (worst-case) space complexity, quick-sort is (Select] merge-sort.

Answer 1

1. Quick Sort partitions the array based on the value of the pivot element. Hence, for partition to take place, it need to place the elements in the correct position with respect to the pivot. Hence, the "divide" part is the place where the main partitioning happens in case of quick Sort.
Merge Sort ,on the other hand, simply divides the array into two equal halves recursively. The4 main sorting part of the algorithm comes afterwards. So, divide part of quick sort is slower than that of merge sort.

Answer: worse than

2. As was discussed in the previous question, divide part of quick sort takes more time than merge sort. However, for merge sort, the main computation occurs after partition. Hence, the Running time for the "conquer" part of quick sort is faster thant that of merge sort.

Answer: better than

3. Worst case Running time of General implementation of Quick Sort is O(n2). Worst case Running time of Merge Sort is O(nlog(n)). Hence, merge sort is quicker.

Answer: worse than

4. For the average case, both quick and merge sort have equal compexities ( O(log(n)) ). Hence, they will take the same time.

Answer: the same as

5. General implementation of merge sort requires extra space to store the left and right subarrays during merging. However, the quick sort algorithm takes no extra space as it can be done inspace. Hence, merge sort has higher space complexity.

Answer: better than

Do give a thumbs up if you are satisfied with this answer to help me out. Thanks! :)